백준 | 퇴사 2

백준 퇴사 2

dp[i]를 'i일까지 근무해서 얻을 수 있는 최대 수익'으로 정의하자.

이제 i일이 되었을 때, i일에 잡힌 상담을 진행할 수 있는지를 따져야 한다.
즉, i일에 진행한 상담의 종료일(i + schedules[i][0] - 1)이 퇴사 일(n + 1) 이전인지 확인해야 한다.

만약 end_date <= n을 만족한다면?
end_date일에 얻을 수 있는 최대 수익을 업데이트해야 하며, 그건 아래의 두 값 중 최댓값이다.

• 다른 상담을 통해 end_date까지 얻은 수익: dp[end_date]
• i일 이전까지 다른 상담을 통해 얻은 최대 수익에 i일 상담 수익을 더한 수익: max_profit + schedules[i][1]

이렇게 1일부터 n일까지의 스케줄을 다 돈 뒤, dp에 저장된 최댓값이 가능한 상담을 모두 진행했을 때의 최대 수익이다.

import sys

# 입력
n = int(sys.stdin.readline())
schedules = [(0, 0)] + [tuple(map(int, sys.stdin.readline().split())) for _ in range(n)]

# dp[i]: i일까지 근무해서 얻을 수 있는 최대 수익
dp = [0] * (n + 1)
# max_profit: 직전 일자까지의 최대 수익
max_profit = 0

for i in range(1, n + 1):
    # 현재까지의 최대 이익 갱신
    max_profit = max(max_profit, dp[i - 1])

    # i일에 잡힌 상담을 진행할 수 있는 경우
    end_date = i + schedules[i][0] - 1
    if end_date <= n:
        dp[end_date] = max(dp[end_date], max_profit + schedules[i][1])

# 출력
print(max(dp))