[백준] 14501. 퇴사 /Python

import sys
sys.stdin = open("input.txt")

def DFS(day,pay):
    global res
    if day == N: #일 수가 N보다 커지면
        if res < pay: #원래있는 페이의 합 보다 크면 갱신
            res = pay
        return
    elif day > N:
        return

    DFS(day+1,pay) #선택 안하는 경우
    if day + L[day][0] <= N: #선택 하는 경우
        DFS(day+L[day][0],pay+L[day][1])


N = int(input()) # N+1되는 날에 퇴사함
# T = []
# P = []
L =[]
for i in range(N):
    t, p = map(int, input().split())
    # T.append(t)
    # P.append(p)
    L.append([t,p])
res = 0
DFS(0,0)
print(res)

---

일단 DFS로 풀었다.

그래서 선택하는 경우, 안하는 경우로 나눴고

먼저 선택 안 하는 경우로 DFS함수를 호출을 한다.

한편,

day가 N과 같을 때 그 pay의 값을 res에 넣어주어 리턴 시킨다.

day > N일 때는 범위를 넘어가므로 그냥 리턴 시킨다.

이제 선택 하는 경우를 보자.

day+걸리는 기간 <= N이면 DFS를 호출 시켜서 재귀를 돌게 한다.