백준 14501 파이썬 python : 퇴사 @@황소처럼 우직하게@@ 재귀로 간단구현

import sys
input = sys.stdin.readline

n = int(input())
days = []
for i in range(n):
    days.append(list(map(int, input().split())))

ans = -999999999

def go(day, total):
    global ans
    if day == n:  # n에 알맞게 도착했을 때, 정답이 될 수 있다.
        ans = max(ans, total)
        return
    if day > n:  # n을 초과한다면 범위 안에 일을 못끝내므로, 정답이 될 수 없다.
        return
    go(day + 1, total)  # 이번 day는 일을 하지 않고 그냥 넘어간다!
    go(day + days[day][0], total + days[day][1])  # 이번 day일을 처리한다, 기간도 점프한다!

go(0, 0)
print(ans)

1. 불가능 : 인덱스 넘어갈때

2. 정답 : 인덱스 끝까지 조사했을 때

3. 다음 : 그냥 넘어가거나 이 일을 하거나

--

모든 그 각각의 day에 대해서

이 day때 일을 했을 때의 재귀를 호출하고

이 day때 일을 안했을 때의 재귀를 호출까지

2번 재귀 호출해줘야해요