14501번: 퇴사
https://www.acmicpc.net/problem/14501
문제 정의
상담을 적절히 했을 때, 백준이가 얻을 수 있는 최대 수익을 구하는 프로그램을 작성하시오.
접근 방법
[나이브한 방법] 1일 상담 -> 4일 상담 -> 5일 상담 2일 상담 3일 상담 -> 4일 상담 -> 5일 상담 4일 상담 -> 5일 상담 5일 상담 모든 경우를 구해서 N개를 N번 순회 -> O(N^2)
[Dynamic Programming 접근 1] 그런데, 살펴보니까 n일 상담 이후의 과정이 동일함을 알 수 있다. 즉, 1일 상담 -> 4일 상담은 무조건 4일 상담-> 의 과정과 동일하다. 1일 상담 + 4일 상담 이후~ 4일 상담 + 5일 상담 이후~ 이런식으로 진행된다. 1, 2, 3, 4, 5, 6, 7일 [10+35(4)], [0+0], [10+35 = 45], [20+15 = 35], 15, 0, 0 -> dp 테이블이 될 수 있다.
문제점: 현재 상담을 했다는 가정하에 dp를 업데이트 하게 된다. 따라서 현재 상담을 건너뛰었을 때 수익이 더 큰데도 불구하고 현재 상담을 진행해 최대 수익이 줄어들 수도 있다.
[Dynamic Programming 접근 최종]
- 현재 상담을 했을 때 VS 현재 상담을 건너 뛰었을 때 중 큰 값의 수익으로 업데이트 해줘야 한다.
- 또한 상담일이 퇴사일을 넘어가면 진행할 수 없으므로, 상담일정표의 뒤에서부터 업데이트 해주면 된다.
풀이
N = int(input()) # N+1에 퇴사함
t_p = [[0, 0]] # [시간, 비용]이 담긴 리스트
for _ in range(N):
t, p = map(int, input().split())
t_p.append([t, p])
# 백준이가 얻을 수 있는 최대 이익을 출력해야함.
dp = [0] * (N+2)
for i in range(N, 0, -1):
tmp = i + t_p[i][0]
if tmp > N+1:
dp[i] = dp[i+1]
else:
dp[i] = max(dp[i+1], t_p[i][1] + dp[tmp])
print(dp[1])
정리
- DP 테이블을 어떻게 업데이트 해야 할 지 아이디어를 처음으로 떠올렸다.
- 하지만 완벽하게 구현하진 못했고, 2%의 부족함이 있었다. → 현재 상담을 건너 뛰었을 때의 예외를 생각하지 못했기 때문이다.
- DP는 더 많이 풀어서 감을 익혀야 할 것 같다. 😭
Uploaded by N2T
