[이코테] 다이나믹 프로그래밍 - 퇴사

해당 포스팅의 문제의 출처는 나동빈님의 이것이 취업을 위한 코딩 테스트 교재를 공부하면서 풀이할 때 본인의 사고 과정 흐름과 문제 풀이를 기록하기 위함 입니다. 

 

---

문제설명

하단의 링크를 참조하자.

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

14501번: 퇴사

사고과정

• DP는 "뒤 입장에서 생각" 해야한다는 관점으로 문제를 풀어보려 했지만 풀지 못했다. 대체 어떻게 점화식을 세워야 하는지 닿을락말락...하지만 닿지 않았음^^
• 풀이를 보니 DP 테이블에는 i일부터 마지막 날(N일)까지 얻을 수 있는 최대 금액을 기록하는 것이었음.
• i일에 상담을 하는데 걸리는 시간 time이 가변적인데 이를 어떻게 해야할지에 대해 막막했음..
• 점화식을 세우는 사람은 천재가 아닌가..? 싶음..

풀이(스스로 못 푼 풀이)

n = int(input())
t = []
p = []
for _ in range(n):
    time, price = map(int, input().split())
    t.append(time)
    p.append(price)

# dp는 i번째 날부터 마지막날까지 낼 수 있는 최대 금액을 DP 테이블에 담기
dp = [0] * (n+1)
max_val = 0
# 뒤쪽부터 계산
for i in range(n-1, -1, -1):
    time = t[i] + i  # ex.6일에 4일짜리 상담이면 10일째부터 새로운 상담 가능
    if time <= n:
        # i일에 상담을 하게 되면 얻는 금액 + i일에 하는 상담에 소요되는 time 이후의 날짜 얻는 최대 금액
        dp[i] = max(p[i] + dp[time], max_val)
        max_val = dp[i]
    else:
        dp[i] = max_val

print(max_val)