백준,퇴사,14501

[유형]

dp

 

[문제링크]

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

 

[요약]

오늘부터 N+1일째 되는 날 퇴사를 하기 위해서, 남은 N일 동안 최대한 많은 상담을 하려고 한다.

각각의 상담은 상담을 완료하는데 걸리는 기간 Ti와 상담을 했을 때 받을 수 있는 금액 Pi로 이루어져 있다.상담을 적절히 했을 때, 백준이가 얻을 수 있는 최대 수익을 구하는 프로그램을 작성하시오.

 

[문제풀이]

dp 테이블을 정의해보자.

i = 근무 가능한 일수

dp[i] = 근무 가능한 일수가 i만큼 남았을 때의 최대 비용

dp[n] = 첫째날부터 마지막날까지 상담을 골라서 했을 때 얻을 수 있는 최대 수익

 

점화식을 정의해보자.

근무가능한 일수 i < 해당 날짜의 상담소요시간이라면, dp[i]=dp[i-1]

근무가능한 일수 >= 해당 날짜의 상담소요시간이라면, dp[i] = max(dp[i-1], 상담으로 버는 수익 + dp[i-상담소요시간])

 

입력을 그대로 받는다면 위 점화식을 사용할 수 없기 때문에, 문제의 입력을 거꾸로 뒤집는다.

import sys
def input():
    return sys.stdin.readline().rstrip()

n = int(input())
s = []

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

s.reverse()
s.insert(0,[])

dp = [0]*(n+1)

for i in range(1,n+1):
    if i < s[i][0]:
        dp[i] = dp[i-1]
    else:
        dp[i] = max(dp[i-1], s[i][1] + dp[i-s[i][0]])


print(dp[n])

 

 

[참고]https://mgyo.tistory.com/673