[BOJ] 퇴사

---

코드

import sys
input = sys.stdin.readline

N = int(input())
t = []
p = []
dp = [0]*(N+1)
for _ in range(N):
    ti, pi = map(int, input().split())
    t.append(ti)
    p.append(pi)

for i in range(N-1, -1, -1):
    ti = t[i]    # 상담 소요일
    if i + ti <= N:    # 근무가능
        pi = p[i]    # 상담수입
        # 퇴사일로부터 바로 다음날(내일)까지의 수입과 오늘 근무할 때의 수입 비교
        dp[i] = max(dp[i+1], dp[i+ti] + pi)  
    else:
        # 근무 불가한 날이면 퇴사일로부터 바로 다음날까지의 수입을 그대로 가져옴
        dp[i] = dp[i+1]

print(dp[0])

결과

풀이 방법

• DP 활용 문제이다.
• 퇴사일로부터 역순으로 오늘까지의 최대 수입을 계산하는 점화식을 구하였다.
• 오늘이 근무 가능한 날인 경우, 퇴사일로부터 내일까지의 수입과 근무 시 오늘까지의 수입을 비교한다.
• 오늘 근무하는 경우의 수입은 오늘 근무할 경우 다음에 근무 가능한 날을 계산하여, 퇴사일로부터 해당 날까지의 수입에 오늘 상담 수입을 더해야 한다.
• 오늘이 근무 불가능한 날이면, 퇴사일로부터 내일까지의 수입을 그대로 가져와서 저장한다.
• 최종적으로 구하는 답은 퇴사일로부터 퇴사 결심일까지의 최대 수입 계산값이다.

---