🧩 알고리즘
[백준] 14501 퇴사 - Python
yeonDev
2022. 11. 16. 14:06
14501번: 퇴사
첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다.
www.acmicpc.net
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])