[dp/백준] 14501번: 퇴사

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

이 문제는 이제 3번째 푸는 거라서 어떻게 풀지 대충 기억이 났다. 

우선 주어진 정보를 역순으로(range(n-1,-1,-1)) 진행한다 

 

-틀린 풀이

i번째 날일 때 일을하고, 일이 끝날 때(t[i]+i) 주어진 날(n+1)을 벗어나지 않는 경우는 새로운 값을 누적하는 것이라고 생각했는데,

여기에 추가해서 값을 비교한 후 더 큰것을 dp[i]에 넣어야한다  

그리고 일이 끝날 때 주어진 날을 벗어나는 경우에 대해서 생각하지 못했다

n=int(input())
t=[]
p=[]
dp=[0]*(n+1)
for _ in range(n):
    a,b=map(int,input().split())
    t.append(a)
    p.append(b)
    
for i in range(n-1,-1,-1):
    if t[i]+i <(n+1):
        dp[i]=dp[t[i]+i]+p[i]
        
print(max(dp))

-정답풀이 

n=int(input())
t=[]
p=[]
dp=[0]*(n+1)
for _ in range(n):
    a,b=map(int,input().split())
    t.append(a)
    p.append(b)
    
for i in range(n-1,-1,-1):
    if t[i]+i <(n+1):
        dp[i]=max(dp[i+1],dp[t[i]+i]+p[i])
    else:
        dp[i]=dp[i+1]
        
print(dp[0])