우선 처음에 이 문제를 접했을 때 가장 처음에 든 생각이 DP로 풀어야하나? 라는 생각이었다.
i까지의 최대비용을 구하고 그걸 N까지로 늘려나가면서 DP리스트의 마지막 값이 최종 결과가 되도록 구현하고자 했다.
DP를 과거에 알고리즘 시간에 배웠었는데 1년전이라 잘 기억이 나지 않았다. 따라서 과거 알고리즘 강의자료를 다시 찾아보면서 학습했다.
문제를 보고 DP를 사용하겠다고 생각했을 때 가장 먼저 떠오른 식은 아래와 같다.
dp[j] = max(dp[j],dp[i]+P[i])현재의 값과 이 상담을 선택했을때의 값을 비교해서 더 큰 값을 dp에 저장하는 방식으로 진행했다.
하지만 반복문의 인덱스를 어떻게 지정해야될지 한참 고민하다가 결국 혼자서 해결하지 못하고 다른 분의 풀이를 참고했다.
DP알고리즘 부분에서 가장 약하다고 느끼고 있었는데 역시 가장 보완해야할 알고리즘이라고 다시 한번 생각하게 되었다.
아래는 제출한 코드이다.
import sys
n = int(sys.stdin.readline())
T = [0 for _ in range(n)]
P = [0]*n
for i in range(n):
T[i], P[i] = map(int,sys.stdin.readline().split())
dp=[0]*(n+1)
for i in range(n):
for j in range(i+T[i],n+1):
dp[j] = max(dp[j],dp[i]+P[i])
print(dp[-1])코드를 보면 i+T[i]부터 끝까지 j를 반복시키는데 i번째에 상담을 진행했다고 가정한다는 의미이다. i번째에 상담을 진행했기 때문에 i+T[i]날부터 퇴사할때까지에 DP에 최대값을 저장하는 것이다.
이를 0부터 n까지 반복하면 최종적으로 dp[-1]에 최대값이 담기게 되는 형식이다.
