boj 15486 : 퇴사2

문제 주소: https://www.acmicpc.net/problem/15486

난이도: silver 1

1.문제설명

• 퇴사하기까지 N일남았다.
• N일동안 최대한 돈을 벌려고한다.
• 일별로 일정이 주어진다.
• 소요기간과 보수가 일정으로 주어진다.
• 이런 정보를 바탕으로 퇴사하기전까지 최대 얼마나 벌수있는지 계산해라
• 돈은 작업이 끝나는날 입금된다.

2.문제해결 아이디어.

• dp로 인덱스에 해당하는 날까지 벌수있는 최대 금액을 기록해보자

3.문제접근법

• 특이하게 dp테이블의 뒷부분(마지막날)부터 시작한다.

for i in range(N-1, -1, -1): #마지막날부터 시작해서
    if schedule[i][0] + i <= N: #(현재날짜의 업무의 소요기간 + 현재날짜)가 퇴사일 이전이면
        dp[i] = max(schedule[i][1] + dp[i + schedule[i][0]], dp[i+1])
        #(현재날짜 업무의 보수 + 업무를했을때 끝나는 날까지 벌수있는 최대금액), 그 일을 선택하지 않았을때 
    else: #현재날짜의 업무 소요기간 + 현재날짜가 퇴사일 이후일때
        dp[i] = dp[i+1] #업무 선택안함

4.특별히 참고할 사항

• 뒤에서부터 업데이트하는 것을 생각하는게 중요하다

5.코드구현

import sys

input = sys.stdin.readline
N = int(input())
schedule = [list(map(int, input().split())) for _ in range(N)]
dp = [0 for _ in range(N+1)]
for i in range(N-1, -1, -1):
    if schedule[i][0] + i <= N:
        dp[i] = max(schedule[i][1] + dp[i + schedule[i][0]], dp[i+1])
    else:
        dp[i] = dp[i+1]
print(dp[0])