<PART 3> Q33. 백준 14501번: 퇴사

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

14501번: 퇴사

 

# 백준 14501번
n = int(input())
t = []
p = []
dp = [0] * (n+1) #dp를 위한 빈테이블
max_value = 0
 
for i in range(n):
    x,y = map(int,input().split())
    t.append(x)
    p.append(y)
 
#리스트를 거꾸로 확인
for i in range(n-1,-1,-1):
    time = t[i] + i
    #상담이 기간안에 끝날 경우
    if time <= n:
        #점화식 대로 계산
        dp[i] = max(p[i]+dp[time],max_value)
        max_value = dp[i]
    #상담 기간을 벗어나는 경우
    else:
        dp[i] = max_value
print(max_value)

처음엔 간단하게 풀 수 있을 거 같았고 t별로 인덱스를 뛰어 넘긴다는 식으로 풀려고 했었다. 그러나 dp문제를 풀때는 그런식으로 접근하면 안된다는 것을 알았다. 불가능한 경우 보다는 가능한 경우의 점화식을 찾고 나중에 불가능한 것들은 조건을 if로 주어서 계산하면 되는 문제였다.
여기서 불가능한 경우는 상담이 기간안에 끝나지 않는 경우이므로 끝날 경우에 점화식을 사용하고, 끝나지 않는다면 그대로 해당 dp값을 출력하면 된다.

나에게는 dp문제 중에서도 낯선 문제였다. 뒤에서 부터 for문을 돌려 기간을 계산할 방법을 떠올리지 못했다. 
dp문제는 점화식을 어떻게든 찾아내서 조건을 생각하는 데에 많은 시간을 들여야겠다.