14501_퇴사

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

14501번: 퇴사

 

 

 

dp를 활용하면 풀 수 있는 문제이다.

 

단 상담 날짜가 안되는게 해당날짜부터 뒤부터 안되므로 dp를 채워나갈 때 뒤에 날짜부터 시작하였다.

 

 

백준의 주어진 입력케이스로 생각해보자.

 

7일 부터 시작해서 과거로 하루씩 늘어난다고 생각하고 이걸 i라고 생각해보자 

 

즉 i 는 1일부터

7,6,5,4,3,2,1 이 된다. (코드로 구현한다면 6,5,4,3,2,1,0으로 구현할 수도 있다.)

 

7일인 경우 i는 1이고 상담에 걸리는 날짜가 2일이기에 추가할 수 없다. 이런식으로 dp를 거꾸로 채워나갈 것이다.

그렇다면 상담을 할순 있는 날짜임을 걸러준다면, 상담에 걸리는 날짜기간을 스킵한 부분 + 현재 상담비용을 계산한 후, 바로 이전dp 값과 비교한다면 점화식을 세울 수 있다.

 

말이조금 어려운데 dp가 채워지는 과정을 한번 보자.

 

[0, 0, 0, 0, 0, 0, 0]

[0, 0, 0, 0, 0, 0, 0]
[0, 0, 15, 0, 0, 0, 0]
[0, 0, 15, 35, 0, 0, 0]
[0, 0, 15, 35, 45, 0, 0]
[0, 0, 15, 35, 45, 45, 0]
[0, 0, 15, 35, 45, 45, 45]

 

dp를 어차피 거꾸로 채워나가기에 Ti,Pi또한 거꾸로 뒤집어서 처음부터 채운다고 생각했다.

 

import sys
input = sys.stdin.readline

day , cost = [],[]
n = int(input())
for _ in range(n):
    a,b = map(int,input().split())
    day.append(a)
    cost.append(b)

day.reverse()
cost.reverse()

dp = [0]*n
dp[0] = cost[0] if day[0]==1 else 0

for i in range(1,n):

    if i>=day[i]-1:
        dp[i] = max(dp[i-1],dp[i-day[i]]+cost[i])
    else:
        dp[i] = dp[i-1]
    print(dp)