[DP] 퇴사2 - 백준

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

15486번: 퇴사 2

 

참고 포스팅

https://j2wooooo.tistory.com/42

 

결국 이 문제 역시 점화식으로 푸는 문제였다.

각 일별 최적의 수익을 정리하기 위해서는 다음 논리로 갈 수 있다.

 

예를 들어

x일 날의 최적의 수익은 다음 중 하나이다.

• x일 상담 끝나는 날짜가 퇴사 일을 넘기는 경우 → x일의 최적의 수익은 x+1일의 최적의 수익과 동일하다 ( dp[x] = dp[x+1] )
• x일 상담 끝나는 날짜가 퇴사 일을 넘기지 않는 경우
  • x일 날 상담을 진행 안 하는 경우 → x일의 최적의 수익은 x+1일의 최적의 수익과 동일
  • ( dp[x] = dp[x+1] )
  • x일 날 상담을 진행할 수 있는 경우 → x일의 최적의 수익은 해당 날짜의 상담을 진행하고 마감 날짜의 최적 수익이 더해지는 경우와 같음
  • ( dp[x] = value[x] + dp[x+times[x]] )
  • 이 중 더 이익이 큰 경우가 x일의 최적의 수익이 된다
  • dp[x] = max(dp[x+1], value[x]+dp[x+times[x]])

이러한 논리로 점화식을 세워 문제를 푸는 것이 논리의 흐름

 

코드 구현은 다음과 같다. 

N = int(input())
times=[0]*(N+2); values = [0]*(N+2); 
for i in range(1,N+1) :
    time, value = [int(x) for x in input().split()]
    times[i] = time
    values[i] = value

dp = [0]*(N+2)

for i in range(N, 0, -1) :
    if i+times[i] > N+1 :
        dp[i] = dp[i+1]
    else : 
        v1 = values[i] + dp[i+times[i]]
        v2 = dp[i+1]
        dp[i] = max(v1, v2)

print(max(dp))