[BOJ/Python] 백준 15486번 - 퇴사2

백준 #15486 퇴사2

15486번: 퇴사 2

import sys
input = sys.stdin.readline

n = int(input())
time = []
pay = []
for _ in range(n):
  t, p = map(int, input().split())
  time.append(t)
  pay.append(p)

profit = [0 for _ in range(n+1)]
for i in range(n-1, -1, -1):
  if i == n-1 and time[i] == 1:
    profit[i] = pay[i]
  elif i + time[i] <= n:
    profit[i] = max(profit[i+1], pay[i] + profit[i+time[i]])
  else:
    profit[i] = profit[i+1]

print(profit[0])

퇴사2여서 기존 퇴사 문제와 조금 다른 내용인 줄 알았는데 아예 똑같은 문제였다.

 

profit 리스트에는 각 날에 얻을 수 있는 최대 이익이 저장되며, 마지막 날부터 최대 이익을 구해나간다.

• 마지막 날은 상담을 완료하는 데 걸리는 기간이 1일이어야만 해당 상담을 할 수 있기 때문에,
  • 기간이 1인 경우에는 최대 이익을 해당 상담의 이익으로 한다.
  • 기간이 1이 아닌 경우에는 0을 저장한다. (profit 리스트를 0으로 초기화된 n+1 크기의 리스트로 만들어서 i+1 값을 넣으면 0을 대입하게 된다.)
• 오늘 날로부터 상담 기간을 더했을 때 퇴사 전에 상담이 가능할 경우, 오늘 상담했을 때 이익과 상담을 하지 않았을 때 이익을 비교하여 더 큰 값을 그 날의 최대 이익으로 저장한다.
  • 오늘 상담을 할 경우 : pay[i] + profit[i+time[i]]
  • 오늘 상담을 하지 않을 경우 : profit[i+1]