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

난이도 SILVER III

문제해결 아이디어

• 스케쥴을 역순으로 순회하는 방법을 선택했다. (정방향으로 순회하면 2차원 dp를 만들어야 될수도 있겠다고 생각해서)
• 해당 일을 기준으로 기간내에 처리 가능한 경우, 해당 일을 처리한 경우와 넘기는 경우 둘 중에서 비교했다.
• 해당 일을 처리한 경우는 기간 이후의 값 dp[i+기간] + 해당일의cost 를 합했고 일을 처리하지 않은 경우 다음날의 dp 값을 가져왔다.
• 기간내에 처리 못하는 경우도 다음날의 dp값을 가져왔다.

소스코드

import sys

input = sys.stdin.readline

n = int(input())

sc = []

for _ in range(n):
    sc.append(list(map(int,input().split())))

dp = [0] * 1015

for i in range(n-1, -1, -1):
    [p, c] = sc[i]

    if p + i <= n:
        dp[i] = max(dp[i+1], dp[i+p] + c)
    else:
        dp[i] = dp[i+1]

print(dp[0])