Python/DP BOJ-14501 퇴사

Posted on | In

[Python/DP] BOJ-14501 퇴사

이 문제를 보고 DP를 써야하는 것을 떠올려야한다.

​ [Dynamic Programming 가정]

  1. 큰 문제를 작은 문제로 나눌 수 있다.

  2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일함

즉, 크고 어려운 문제가 있으면 잘게 나눠 문제를 해결한 후 전체의 답을 구함.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
N = int(input()) # 일하는 기간
T, P = [], [] # 상담시간/ 금액
for _ in range(N) :
    t,p = map(int,input().split())
    T.append(t)
    P.append(p)

d = [0] * (N+1) # memoization
for i in range(N-1, -1,-1):
    # 상담시간이 퇴사일을 넘길 경우, 상담하지 않음
    if i + T[i] > N :
        d[i] = d[i+1]
    # 기록된 정보를 토대로 큰값을 선택 
    else :
        d[i] = max(d[i+1], P[i]+d[i+T[i]])
print(d[0])

Reference

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

DP 알고리즘 설명 영상 : https://www.youtube.com/watch?v=FmXZG7D8nS4

풀이 참고 : https://ahn3330.tistory.com/82