백준 14501번 파이썬 문제풀이(브루트 포스 - 퇴사)

코드

# n+1일째 되는 날 퇴사
n = int(input())
t = [0] * (n + 1)
p = [0] * (n + 1)

answer = 0

for i in range(1, n + 1):
    t[i], p[i] = map(int, input().split())


def go(day, sum_):
    global answer

    # 종료조건: 퇴사날에 딱 맞췄을 때
    if day == n + 1:
        answer = max(sum_, answer)
        return

    # 불가능한 경우: 상담을 했을 때, 퇴사날을 넘어가는 경우
    if day > n + 1:
        return

    # 상담을 한다
    go(day + t[day], sum_ + p[day])

    # 상담을 안한다
    go(day + 1, sum_)


go(1, 0)
print(answer)

-> 아무리 생각해도 혼자서 이걸 재귀로 생각한다는건 쉽지 않은거 같다.

이 문제의 핵심은 조건이 N+1 일때 return한다는 것과 n+1보다 클때도 Return 한다는것 이 두가지를 생각해야 한다.

또한 상담을 할때와 안할때(그냥 다음날로 넘어가는경우)를 분기해서 재귀를 돌려야한다는 것도 상당히 어려운 부분이다.

 

다음은 위와 같은 코드이지만 이중리스트에 저장해놓고 푼 코드이다. 

N = int(input())
array = [[0, 0]]
for _ in range(N):
    T, P = map(int, input().split())
    array.append([T, P])

result = 0


def solve(day, sum_):
    global result
    if day == N + 1:
        result = max(result, sum_)
        return
    if day > N + 1:
        return

    solve(array[day][0] + day, sum_ + array[day][1])

    solve(day + 1, sum_)


solve(1, 0)
print(result)