[python] 백준 14501 퇴사

https://www.acmicpc.net/problem/14501

14501번: 퇴사

 

 

문제 해결

i번째 일의 상담을 했을 때 k일이 걸린다면 i+k-1일까지는 상담을 못한다. 따라서 i+k일의 상담부터 할 수 있다.

i+k일의 상담을 할 수 있어도 만족스럽지 않으면 안하고 i+k+1일로 넘어갈 수 있다.

상담은 n일 까지 끝내야 하므로 주의한다. (아래 코드는 0일부터 n-1일로 했다. 그러므로 이해할 때 -1일을 더하면 된다.)

 

CODE

import sys
input = sys.stdin.readline

n = int(input())
schedule = [list(map(int, input().split())) for _ in range(n)]
ans = 0
def solve(i,score):
    global ans
    if i==n:
        ans = max(ans,score)
        return
    for j in range(i,n):
        if j+schedule[j][0]-1 <n:
            score += schedule[j][1]
            solve(j+schedule[j][0], score)
            score -= schedule[j][1]
        else:
            ans = max(ans,score)
    return
solve(0,0)
print(ans)