[백준] 14501 - 퇴사 (DP)

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

14501번: 퇴사

n = int(input())
 
answer = [list() for _ in range(n + 1)]
for ans in answer:
    ans.append(0)
    ans.append(list())
 
for i in range(n):
    day, money = map(int, input().split())
    if 0 < day + i <= n:
        answer[day + i][1].append([day, money])
 
for i in range(1, n + 1):
    if answer[i - 1][0] > answer[i][0]:
        answer[i][0] = answer[i - 1][0]
    for day, money in answer[i][1]:
        if answer[i][0] < answer[i - day][0] + money:
            answer[i][0] = answer[i - day][0] + money
 
print(answer[-1][0])

실버 문제인데 꽤나 오래 고생했다.

 

일단, 돈은 일을 마친 다음 날 받는다고 가정했다.

그리고, 각 날짜에 어떤 일을 마칠 수 있고, 그 돈은 얼마인지 저장해두고, 둘째날부터 계산했다.

max(전날까지 번 돈, n일 전에 시작했다면 오늘 돈을 받을 경우, 합계)

이런 식으로 하면 각 날짜마다 최대로 받을 수 있는 날짜로 DP 접근을 할 수 있다.