악 DP!!

#14501번 퇴사 https://www.acmicpc.net/problem/14501

14501번: 퇴사

여러 방법을 시도했지만 자꾸 부분정답이 나왔다. 

 

부분 정답이 나올 때에는 과감하게 갈아엎는 것도 나쁘지 않다고 생각한다.

 

나는 잡고 늘어지다가 결국엔 구글링...

 

솔루션은 신기했다

dp를 거꾸로, 맨 뒤 index부터 접근하는 방식이었다.

아무래도 그렇게 하는게 날짜를 계산하기 쉽겠지...

 

dp의 길이는 날짜보다 1 더 길다.

초기값인 0을 설정해주기 위해서다.

 

앞서 말했듯 뒤에서부터 진행한다.

현재 날짜 (일을 받은 날짜)에 일을 진행하는 기간(d)을 더했을 때, N을 초과하면 안된다.

초과할 경우에는 (작업을 진행할 수 없다.) 오른쪽에 있는 값을 넣어준다. (시작은 0)

작업을 진행할 수 있는 경우에는 최댓값을 구해주는데

 

작업을 진행하지 않고 오른쪽에 있는 값을 그대로 받았을 경우 : dp[i+1]

작업을 진행할 경우 :  작업의 이익 + 현재날짜로부터 작업기간이 지난 날이 갖고있는 dp값

 

중 큰 값을 저장해주면 된다.

 

결과적으로는 0번 인덱스에 최댓값이 저장된다.

import sys
N = int(input())
profits = [0]*N
times = [0]*N
for i in range(N):
    t, p = map(int, sys.stdin.readline().split())
    if t <= N-i:
        profits[i] = p
        times[i] = t

dp = profits + [0]

for i in range(N-1, -1, -1): # 뒤에서 부터 진행
    if times[i] + i > N:    # 현재 날짜 + 진행일수 > N일 경우에는 -> 작업 진행 불가
        dp[i] = dp[i+1]     # 오른쪽에 있는 값 저장 (초기 0)
    else:                   # 작거나 같을 때 -> 작업 진행 가능
        # 작업을 진행 할 경우와 진행하지 않을 경우의 이익을 비교해서 큰 값으로 넣어줌
        dp[i] = max(dp[i+1], profits[i] + dp[i+times[i]])
                            # 작업을 진행 할 경우는 작업이익과 진행일수가 지난 시점의 이익을 더해줌

print(dp[0])

 

dp를 풀어본 기억이 좀 되어서인지 dp리스트에는 각 인덱스에 해당하는 정답을 넣어야만 한다고 생각했던게 문제였던 것 같다.

dp에는 "필요한 값"만 들어가면 되는 듯 하다.