[백준] 15486번 : 퇴사 2

15486번: 퇴사 2

15486번: 퇴사 2

🤔 문제분석

1차원 dp 테이블을 가지고 문제를 해결 할 수 있다. 시간과 금액을 순회하는데 i번째 순회에서의 dp값을 갱신하는 방법은 dp[i+t] = 현재까지의 최대가치 + p로 표현할 수 있다. 해당문제는 현재까지의 최대 가치를 생각해내는 것이 제일 중요한 포인트이다.

예를들어 아래의 표를 살펴보자, i가 5일때 생각해보면, dp[5+5일의시간] = 5일까지 최대 갖을 수 있는 금액 + 5일의 금액 으로 표현 할 수 있다.

💻 코드

import sys
input = sys.stdin.readline

N = int(input())

dp = [0 for _ in range(N+2)]
prev = 0

for i in range(1, N+1):
    t, p = map(int, input().split())
    
    if dp[i] > prev:
        prev = dp[i]
        
    if N+1 >= i + t:
        dp[i+t] = max(dp[i+t], prev + p)

print(max(prev, dp[N+1]))

🎯 피드백 및 개선사항

이번문제도 다이나믹 프로그래밍 유형중 하나로, 여러가지 방안으로 생각해보며 어떻게 문제를 풀지 고민하는 시간이 저에게 큰 도움이 된 것 같습니다. 점점 다이나믹 프로그래밍 문제에 자신감을 갖게 되는것 같습니다 👏👏👏