이 문제는 누적 합이 최대가 되는 경우를 구하는 문제이기 때문에 DP를 사용한다.
핵심 원리: (과거에 모은 돈) + (오늘 번 돈) 으로 계속 갱신해나간다.
import sys
input = sys.stdin.readline
n = int(input()) # 근무일(1일~n일)
dp = [0]*(n+1) # i번째 날까지 일했을 때 최대 수익
for i in range(1, n+1):
t, p = map(int, input().split()) # t일, 수익P
dp[i] = max(dp[i], dp[i-1]) # 현재 날까지의 최대 수익 vs 전날까지의 최대 수익
if i+t-1 <= n:
dp[i+t-1] = max(dp[i+t-1], p + dp[i-1]) # 상담을 마친 날의 최대 수익 vs 그 날의 기존 최대 수익 + 현재 날의 전까지의 최대 수익
print(dp[-1 // 마지막 요소 출력 | 날짜(i) | 기간(T) | 금액(P) | 1단계: 오늘 수익 갱신 (i날짜 까지 번 돈(전날 이월) | 2단계: 미래 수익 갱신 (상담 끝나는 날 dp[i+t-1] 찜하기) | 현재 dp 배열 상태 ( dp[1] ~ dp[7]) |
|---|---|---|---|---|---|
| 1일 | 3 | 10 | dp[1] = 0 | 3일차(dp[3])에 저장값: 0(어제) + 10 = 10 | [0, 0, 10, 0, 0, 0, 0] |
| 2일 | 5 | 20 | dp[2] = 0 | 6일차(dp[6])에 저장값: 0(어제) + 20 = 20 | [0, 0, 10, 0, 0, 20, 0] |
| 3일 | 1 | 10 | dp[3] = 10 | 3일차(dp[3])에 저장값: 0(어제dp[2]) + 10 = 10(기존 10과 같아 변동 없음) | [0, 0, 10, 0, 0, 20, 0] |
| 4일 | 1 | 20 | dp[4] = 10(3일차 값 이월) | 4일차(dp[4])에 저장값: 10(어제dp[3](=3알차까지 번 돈)) + 20 = 30👉 30으로 갱신! | [0, 0, 10, 30, 0, 20, 0] |
| 5일 | 2 | 15 | dp[5] = 30(4일차 값 이월) | 6일차(dp[6])에 저장값: 30(어제dp[4]) + 15 = 45👉 기존 20보다 크므로 45로 갱신! | [0, 0, 10, 30, 30, 45, 0] |
| 6일 | 4 | 40 | dp[6] = 45(기존 값 유지) | 9일차(dp[9]) 저장?👉 퇴사일(7) 넘음. 무시 | [0, 0, 10, 30, 30, 45, 0] |
| 7일 | 2 | 200 | dp[7] = 45(6일차 값 이월) | 8일차(dp[8]) 저장?👉 퇴사일(7) 넘음. 무시 | [0, 0, 10, 30, 30, 45, 45] |
