[백준] 14501번 퇴사 _ python

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

재귀로 풀려고 시도했는데 너무 복잡하게 생각해서 실패..
그냥 Brute force 재귀로 풀거면 어차피 다 탐색하는 거니까 최대한 간단하게 생각해야 할 듯 하다.
다른 분 풀이 참고해서 작성해본 코드는 다음과 같다.
이렇게 작성하면 퇴사날 딱 맞추지 않았을 때 result는 어떻게 저장하나 생각했는데 어차피 상담 안 한 경우도 재귀로 따로 따지니까 다 포함된다. -> 상담 안 하면 now만 +1 해서 재귀 도니까 무조건 퇴사날 맞출 수 있음.

풀이1 - 재귀 활용 Brute Force

import sys
sys.setrecursionlimit(10000)

n = int(sys.stdin.readline())
meet_lst = []
for i in range(n):
    d, t = map(int, sys.stdin.readline().split())
    meet_lst.append((d,t))
result = 0

def meeting(now, pay):
    global result
    if now == n+1:	# 종료 조건1 : 퇴사날 딱 맞췄을 때
        result = max(result, pay)
        return
    if now > n+1:	# 종료 조건2 : 퇴사날 지났을 때
        return

    meeting(now+meet_lst[now-1][0], pay+meet_lst[now-1][1])     # 상담o
    meeting(now+1, pay)      # 상담x

meeting(1, 0)
print(result)

풀이2 - DP

아직 DP가 익숙하지 않아서 그런지, 이 방법이 더 이해도 어렵고 떠올리기도 어렵겠다는 생각을 했다. 코드는 훨씬 깔끔하고, 많은 분들이 이 방법으로 풀었다. 시간복잡도도 더 작다. 공부를 더 해 봐야겠다.
DP로 뒤부터 계산해주면 되는 방법이다.

import sys

N = int(sys.stdin.readline())
T, P = [], []
for _ in range(N):
    t, p = map(int, sys.stdin.readline().split())
    T.append(t)
    P.append(p)

d = [0] * (N+1)

for i in range(N - 1, -1, -1):
    # i일에 상담을 하는 것이 퇴사일을 넘기면 상담을 하지 않음
    if i + T[i] > N:
        d[i] = d[i+1]
    else:
        # i일에 상담을 하는 것과 상담을 안하는 것 중 큰 것을 선택
        d[i] = max(d[i+1], P[i] + d[i + T[i]])

print(d[0])