백준 15486 : 퇴사 2

https://www.acmicpc.net/problem/15486

15486번: 퇴사 2

 

해결 방법 : DP

• i일차에 주어진 상담 기간 T, 상담 비용 P에 대해, dp[i + T]를 갱신해주면 된다.
  
  • 점화식 : dp[i + T] = max(dp[i + T], dp[i] + P)
    • i + T 가 퇴사 이전인 경우에만 갱신한다.
• i일차의 최고 수입은 현재까지의 최고 수입이므로, 동기화 작업이 필요하다.
  • dp[i] = max(dp[i], dp[i-1])

import sys
input = sys.stdin.readline

def solution(N, arr):
    dp = [0] * (N + 1)
    
    for i, TP in enumerate(arr):
        T, P = TP # 상담 기간, 비용
        dp[i] = max(dp[i], dp[i-1]) # 현재까지 최고 수입으로 동기화
        if i + T <=  N: # 상담 가능 
            dp[i + T] = max(dp[i + T], dp[i] + P) # 점화식

    return max(dp[N-1], dp[N])

if __name__ == '__main__':
    N = int(input())
    arr = [tuple(map(int, input().split())) for _ in range(N)]
    result = solution(N, arr)
    print(result)