[Baekjoon 15486 / python / 골드5] 퇴사2

# 1일차의 최댓값, 2일차의 최댓값, 3일차의 최댓값.. 순으로 N일차의 최댓값까지 구한다

import sys

input = sys.stdin.readline

#  상담 가능 일수

N = int(input())

# 시간과 수익을 따로 입력받는다

time, point = [0 for _ in range(N + 1)], [0 for _ in range(N + 1)]

for i in range(1, N + 1):

    time[i], point[i] = map(int, input().split())

# dp 테이블 만들고, 1일부터 로직 시작

dp = [0 for _ in range(N + 1)]

for i in range(1, N + 1):

    # 기존에 있던 값과 전날 값을 비교해 큰 값으로 설정한다. 기존 값은 finDate에 의해 이미 설정되었을 수 있기 때문

    dp[i] = max(dp[i], dp[i - 1])

    finDate = i + time[i] - 1  # i일 상담이 끝나는 날짜

    if finDate <= N:  # 상담이 가능하다면, 상담 끝나는 날짜에 수익을 추가한다. 단, 기존 값보다 더 클 경우.

        dp[finDate] = max(dp[finDate], dp[i - 1] + point[i])

print(max(dp))

 

다이나믹 프로그래밍 문제이다.

 

1일 ~ N일까지 각각 상담이 1개씩 잡혀 있으며, 각 상담은 상담에 걸리는 날짜와 수익이 다르다.

N일까지의 상담을 적절하게 맡아서 최대 수익을 얻어야 하는 문제이다.

 

이 문제는 작은 일수부터 최댓값을 구해나가서 N일까지의 최댓값에 도달하면 된다. 즉, 

1일까지의 최댓값

2일까지의 최댓값

....

N일까지의 최댓값

이런 식으로 DP를 구현하면 된다.

 

날짜는 1일부터 있으므로 time, point, dp테이블을 N + 1 크기로 만들고 반복문을 1부터 시작한다.

dp테이블엔 i일 까지의 최대 수익이 각각 저장된다.

 

반복문이 시작되는 i일의 최대 수익은, "max(dp[i], dp[i - 1])" 으로 설정한다. dp[i]값은 아래쪽 finDate에 의해서 이미 저장되었을 수 있기 때문에 가능하다.

 

상담이 끝나는 날을 구하는 식은

"i + time[i] - 1" 이다. 이러면 해당 날짜의 상담이 끝나는 날이 구해지며 이것은 finDate에 저장된다. 해당 날짜 상담의 수익을 전날의 수익에 더해서, dp[finDate]에 넣어주면 된다. 물론 기존 값보다 클 경우이다. 따라서 식은,

"dp[finDate] = max(dp[finDate], dp[i - 1] + point[i])" 이다.

 

이렇게 반복문을 돌며 dp[i] 값과 dp[finDate] 값을 계속 갱신해 주는데, 항상 max함수를 사용해 더 큰 값을 저장하므로 dp 테이블엔 항상 최댓값이 저장되게 된다. 앞의 날짜까지의 최댓값을 이용해 오늘의 최댓값을 구하므로 dp형식에 들어맞는다.