[백준] 14501 퇴사 - Python

14501번: 퇴사

POINT

Dynamic Programing (dp)

피보나치 수열이 대표적인 예시이다. 1. 큰 문제를 작게 나눌 수 있고, 2. 작은 문제에서 구한 결과가 큰 문제에서도 사용되면 Dynamic Programing을 사용한다. 재귀(Top-down), 반복(Bottom-up) 두 가지 방법이 있으며, 시간 복잡도를 고려해서 보통 반복문을 사용한다.

풀이

• 특이한 점은 dp를 거꾸로 적용해야 한다는 점이다.
• i 번째 날 수익이 그 이후 i + t번째 날에 영향을 받기 때문이다.

 

• i 번째 날의 수익을 더할지 말지 판단할 때, 그 상담이 끝난 후가 퇴사 전이어야 수익을 더할 수 있다.
• 반대로 i 번째 날 상담이 끝나기 전에 퇴사한다면, 그 날 수익은 다음 날 수익을 그대로 가져온다.

 

• dp에 거꾸로 저장할 때는 입력받은 N개의 데이터를 0 ~ (N-1)에 저장한다.

 

입력 예시를 사용하여 아래 코드를 수행한 dp의 결과는 다음과 같다.

 

T	3	5	1	1	2	4	2
P	10	20	10	20	15	40	200
index	0	1	2	3	4	5	6	7
dp	45	45	45	35	15	0	0	0

N = int(input())
T = []
P = []
dp = [0] * (N+1)

for _ in range(N):
    t, p = map(int, input().split())
    T.append(t)
    P.append(p)
    
for i in range(N-1, -1, -1):
    # 퇴사 하기 전에 상담이 끝나지 않으면
    if i + T[i] > N:
        dp[i] = dp[i+1]
    
    # 상담이 끝나도 퇴사 전이면
    else:
        dp[i] = max(dp[i+1], dp[i+T[i]] + P[i])
        
print(dp[0])