[Python] 백준 14501번 : 퇴사

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

14501번: 퇴사

---

 문제 풀이

전형적인 DP 문제이다.

DP 문제를 해결할 때에는 점화식이 중요하다. 이 문제는 점화식 자체는 단순하다.

DP[i]는 i 번째 날에 최대 금액이다. 

점화식은 일을 받았을 때, 일을 해결한 날의 DP 값과 받기 전 날 DP 값과 받은 일의 금액의 합을 비교해야 한다.

x는 일을 해결하는데 걸리는 기간

이 문제는 몇 가지 센스를 요구한다고 생각하는데

첫 번째는 DP 리스트의 크기이다. 

 최대 걸리는 기간은 5일이므로 DP는 n+5 크기를 가져야 한다.

두 번째는 상담 처리에 대한 것이다.

 n일에 3일이 걸리는 일을 시작했을 때, n+3일째에 새로운 일을 받을 수 있다.

 하지만 금액은 n+2일에 정산된다고 생각할 수 있기 때문에 하루 전 날자로 계산해야 한다.

 느낀 점

이번에 DP 문제를 풀고선 수학적으로 많이 부족함을 느꼈다. 

점화식을 구하는게 그렇게 어렵지 않았는데 막막했따.. ㅠ.ㅠ

다른 분들은 뒤에서부터 시작하시는데 난 그게 싫어서 앞에서부터 확인하도록 구현했다!

 코드

import sys

n = int(input())
timetable = [[0,0]]
for i in range(n):
    t, p = map(int, sys.stdin.readline().split())
    timetable.append([t, p])
DP = [0] * (n + 5)

for i in range(1, n+1):
    DP[i] = max(DP[i-1], DP[i])
    DP[i + (timetable[i][0] - 1)] = max(DP[i + (timetable[i][0] - 1)], DP[i-1] + timetable[i][1])
    
print(DP[n])