[파이썬, Python] 백준 14501: 퇴사

문제

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

14501번: 퇴사

코드

n = int(input())
t = list()
p = list()
dp = [0] * (n+1)

for _ in range(n):
    a, b = map(int, input().split())
    t.append(a)
    p.append(b)

for i in range(n-1, -1, -1):
    if t[i] + i > n:
        dp[i] = dp[i+1]
    else:
        dp[i] = max(p[i] + dp[i + t[i]], dp[i+1])

print(dp[0])

설명

우선 입력값을 다 받아주고 dp 리스트를 [0]으로 n+1개 만들어준다.

2가지 경우를 고려해야 하는데,

1. 오늘의 상담을 하는 경우
2. 상담을 하지 않는 경우

1번의 경우 오늘 상담보상과 이전까지 쌓여있던 보상이 되고,
2번의 경우 지금까지 쌓인 보상이 된다.

그런데 처음부터 계산을 하게 될 경우 퇴직일을 넘긴 상담일자를 거르기 어렵고,
시간계산에 어려움이 생기게 된다.

따라서 뒤에서부터 계산을 해야 한다.

그렇게 된다면,
1번의 경우 오늘 상담 보상과 dp[i + t[i]]를 합친 값
(i가 4일 경우, dp[4 + t[4]] = dp[4 + 1] = dp[5],
따라서 p[5] + dp[5] = 15 + 0 = 15)
=> 오늘의 상담을 진행했을 때, 진행할 수 있는 나머지의 값 중 최대치

2번의 경우 dp[i+1],
즉 기존까지의 최대치가 된다.

상담 일자가 퇴직일을 넘어가는 경우도 고려해야 하는데,
이는 2번과 같이 기존의 최대치가 된다.

따라서 dp를 역순으로 계산해 주고 dp[0]을 출력해 주면 된다.