[백준][파이썬]14501번: 퇴사

문제 출처 : https://www.acmicpc.net/problem/14501

14501번: 퇴사

내 풀이

n = int(input())

t_list = []
p_list = []
answer = [0] * (n + 1)

for i in range(n):
    t, p = map(int, input().split())
    t_list.append(t)
    p_list.append(p)

for i in range(n - 1, -1, -1):
    if t_list[i] + i > n:
        answer[i] = answer[i + 1]
    else:
        answer[i] = max(p_list[i] + answer[i + t_list[i]], answer[i + 1])
        
print(answer[0])

설명

dp문제라고 한다.

!!!!뒤!!!! 부터 계산을 해주면 되는데 만약

1. 상담이 끝나는 날이 n을 넘어가게 되면 일을 맡을 수 없기 때문에 dp[i] = dp[i + 1]

2. 그 외의 부분에는

(1)[현재 일을 맡았을 때 들어오는 보상 + 현재 일을 끝낸 다음날에 쌓여있는 보상]

(2)일을 맡지 않을 경우 보상

둘을 비교

max(p_list[i] + answer[i + t_list[i]], answer[i + 1])

하여 큰 값을 받아주면 된다.