[baekjoon] 백준 15486 퇴사2

문제

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

15486번: 퇴사 2

풀이

• 끝나는 날 기준으로 얻을 수 있는 금액을 입력 - 끝나는 날 기준이기때문에 N+1일까지 반복
• 상담일자와 상담기간을 더했을 때 퇴사 일자를 넘어가면 continus
• 이전의 저장된 k의 값과 dp[i] 중 비교하여 큰 것으로 갱신
• dp[i] 는 현재까지의 수익 + 이번 상담 수익 vs 오늘의 상담이 끝나는 시점의 수익 중 큰 값 저장

T/P	1일	2일	3일	4일	5일	6일	7일	8일
3 / 10				10
5 / 20						20
1 / 10				10
1 / 20					10+20
2 / 15							10+20+15
4 / 40								continue
2 / 200								continue

코드

# 상담 N일동안 최대한 많은 상담
# 상담 완료 기간 T/ 상담을 했을 때 받을 수 있는 금액 P
# 가치 구하기, 배낭문제와 같음
import sys 

n = int(sys.stdin.readline())
t, p = [], []
dp = [0] * (n+1)

for _ in range(n):
    ti, pi = map(int, sys.stdin.readline().split())
    t.append(ti)
    p.append(pi)

k = 0
for i in range(n):
    k = max(k, dp[i])
    if i + t[i] > n:
        continue
    dp[i + t[i]] = max(k + p[i], dp[i + t[i]])

print(max(dp))