백준 15486 퇴사 2

문제 : 15486

풀이 point

다이나믹 프로그래밍을 활용한다.

dp 배열을 통해, dp[i] # i일째가 되었을 때 가장 최고 가치를 표시한다.

경우의 수를 두가지로 나눌 수 있다.

1. i번째 일을 선택하는 경우
2. 선택하지 않는 경우

이는 다음과 같은 수식으로 나타낼 수 있다.

dp[i+i번째 일을 할때 걸리는 기간] =
max(지금까지 최고 가치+i번째 일을 하면 얻는 가치, dp[i+i번째 일을 할때 걸리는 기간])

풀이 코드

#백준 15486 퇴사 2

import sys
input = sys.stdin.readline

N = int(input())

schedule = []
dp = [0]*(N+1)

for i in range(N):
    schedule.append(list(map(int, input().split())))

maxP = 0
for i in range(N):
    t, p = schedule[i][0], schedule[i][1]
    maxP = max(maxP, dp[i])
    if i + t > N:
        continue
    dp[i+t] = max(maxP+p, dp[i+t])

print(max(dp))

maxP는 지금까지 구한 값 중 최대를 의미한다.(dp[i-1]과 같다.)

사족

경우의 수인걸 눈치채서 거의 다 왔는데... 조금만 더 생각했으면 싶다...