boj-14501 퇴사

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

n = int(input())
t=[] #시간,비용
for i in range(n):
    m,w=map(int,input().split())
    t.append((m,w))
max_value=0

def dfs(idx,value):
    global max_value
    if idx==n:
        if max_value<value:
            max_value=value
        return
    dfs(idx+1,value)
    if idx+t[idx][0]<=n :
        dfs(idx+t[idx][0],value+t[idx][1])
dfs(0,0)
print(max_value)

문제는 쉬웠는데

 

최초 풀이에서 틀린 부분 찾는 것과 시간초과 이유를 찾는데 시간이 오래걸렸다.

DFS로 모든 경로를 돌게하는 것이 아닌 DP재귀로 필요한 부분에만 접근하게하는 것이 시간초과의 이유였다.

for문이 필요 없었던 문제였다.