[백준/dp] 14501번: 퇴사(2차)

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

 

이전에 풀었던 풀이는 여기에 있다 

여기에서 t[i]+i를 왜 하는지 모르겠다고 되어있는데, 이는 간단하다. i번째 날에 상담을 했다면 상담을 끝난 날부터 다른 상담을 할 수 있으므로, 다음 상담을 할 수 있는 날이 i+t[i]인 것이다. 이때의 상담료를 보면된다 

 

-정답 풀이: 

풀이 방법으로 0번부터 차례로 상담가능한 날짜들을 기준으로 상담료를 더하는 것으로 생각했다. 

그리고 index+data[index][0]인 날을 기준으로 또 상담을 진행하는 것이라고 생각했다. 

여기서 고민되었던 게, i+t[i]일부터 상담을 할 수 있다는 것이지, 이날에 꼭 상담을 해야하는 것은 아니다. 

이 이후에 날에 기간내에 끝낼 수 있고, 더 많은 돈을 벌 수 있는 날이 있을 수 있기에 순차적으로 하기엔 어렵다고 생각했다. 

그래서 잘 풀리지 않아서 답지를 봤다 

 

일단 순서는 끝 인덱스부터 시작해야 한다.(for i in range(n-1,-1,1))

인덱스가 거꾸로 가므로 max_value는 dp[i+1]을 의미. 

 

n=int(input())
t=[]
p=[]
dp=[0]*(n+1)
max_value=0

for _ in range(n):
    x,y=map(int,input().split())
    t.append(x)
    p.append(y)
    
for i in range(n-1,-1,-1):
    time=t[i]+i
    if time <= n:
        dp[i]=max(p[i]+dp[time],max_value)
        max_value=dp[i]        
    else:
        dp[i]=max_value
print(max_value)