[백준] 14501번 : 퇴사 (파이썬)

문제

나의 답안

import sys
input = sys.stdin.readline

n=int(input())
t,p=[],[]
mx=0
dp=[0]*(n+1)

for i in range(n):
    a,b=map(int,input().split())
    t.append(a)
    p.append(b)

for i in range(n-1,-1,-1):#뒤쪽부터 접근
    day=t[i]+i#현재 날짜에 해당하는 소요기간+현재 날짜
    
    if day<=n:#상담이 퇴사 전 기간 안에 끝나면
        dp[i]=max(p[i]+dp[day],mx)
        mx=dp[i]
    else:
        dp[i]=mx
print(mx)

접근 방법

• 뒤쪽 날짜부터 접근 해야 한다. (n+1일에는 일을 할 수 없으므로)
  유사 문제
• 뒤쪽 날짜부터 매일 현재 날짜의 이익 + 현재 상담을 마친 날짜부터의 이익을 계산해주어 현재까지의 이익과 계산 한 값 중 최대값을 도출해내면 된다.
  즉, max(p[i]+dp[t[i]+i],mx)
• 만약 상담이 기간 전에 끝나지 않는다면, 현재까지의 이익을 반환해주면 된다.