[백준/Python] 15486번 : 퇴사 2

문제

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

---

풀이

퇴사날 얻을 수 있는 가장 큰 이익은 다이나믹 프로그래밍을 활용하여 각 날짜까지 얻을 수 있는 최대 이익을 구하면 된다.
각 날까지 얻을 수 있는 이익을 0으로 초기화 시킨 배열 dp를 생성한다.
첫 날부터 일정 상담 시간 이후에 얻을 수 있는 금액을 구한다.
상담 종료 일정에 맞춰 그날 얻을 수 있는 총 금액을 구한다.
상담 시작일 이전까지 얻을 수 있는 최대 이익에 현재 상담 이익을 더하여 업데이트 한다.
가장 큰 이익을 출력한다.

---

코드

N = int(input())
chart = [list(map(int, input().split())) for _ in range(N)]
dp = [0 for _ in range(N+1)]
cur_max = 0

for i in range(N):
    cur_max = max(cur_max, dp[i])
    if chart[i][0]+i+1 <= N+1:
        dp[i+chart[i][0]] = max(dp[i+chart[i][0]], chart[i][1]+cur_max)

print(max(dp))