[알고리즘/백준] 14501번 : 퇴사(python)

두가지 경우로 나누어서 풀면 된다. 선택하는 경우, 선택 안하는 경우
선택을 하지 않으면 날짜에서 +1을 해준다.
선택을 하면 day+소요날짜를 더한게 N보다 작으면 백트래킹 실행
'==' N인 이유는 7일이 되면 계산하기 위해서

def dfs(day, tmp):
    global ans
    if day == N:
        if ans < tmp:
            ans = tmp
        return
    dfs(day+1, tmp)
    if day + a[day][0] <= N:
        dfs(day+a[day][0], tmp + a[day][1])


N = int(input())
a = [list(map(int, input().split()))for _ in range(N)]
ans = 0
dfs(0, 0)
print(ans)