백준 퇴사 코드 및 해설 (파이썬)

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

14501번: 퇴사

 

각 날짜까지의 누적 이익을 담은 dp 리스트를 만들고, 다이나믹 프로그래밍으로 풀이했습니다. 처음엔 모두 0으로 초기화합니다. 입력을 받으면서 start는 현재 일이 시작되는 날, end는 현재 일이 끝나는 날, profit은 현재 일로 얻을 수 있는 이익으로 정의합니다.
(현재 일이 시작되기 전까지의 이익 + 현재 일을 끝낸 후의 이익)과 (일이 끝나는 날의 기존 dp 값) 중 큰 값을 dp[end]로 갱신합니다.
이때 end+1일 이후의 누적 이익이 end일까지의 누적 이익보다 적을 수 없으므로 , dp[end+1:]의 모든 값을 현재 자신의 값과 갱신된 dp[end] 값 중 큰 것을 취하도록 합니다.
마지막으로 dp의 마지막 요소를 통해 마지막 날의 최대 이익을 반환합니다.

 

import sys

# 퇴사 전 남은 일 수
N = int(sys.stdin.readline())
dp = [0] * (N+1)

for i in range(N):
    # 소요일자, 이익 
    t, profit = list(map(int, sys.stdin.readline().split()))
    # 일이 끝나는 날, 일이 시작되는 날
    end, start = i+t, i+1

    if end in range(len(dp)) and start-1 in range(len(dp)):
        # (현재 일이 시작되기 전까지의 이익 + 현재 일을 끝낸 후의 이익)과 (일이 끝나는 날의 기존 dp 값) 중 큰 값을 취함  
        dp[end] = max(dp[start-1] + profit, dp[end])
        # 이익이 줄어들 수는 없으므로 
        for j in range(end+1, len(dp)):
            dp[j] = max(dp[j], dp[end])

# 마지막 날의 최대 이익 
print(dp[-1])