백준 #14501 - 퇴사 : DP

(구현 : python3)

DP : "케이스마다 최적의 해를 저장하면서 다른 케이스의 최적해를 활용해여 새로운 케이스의 최적해를 찾아나가는 방식" 이라고 설명할 수 있습니다.

아이디어는 다음과 같습니다.

X일부터 일을 시작했을 때 가장 많이 벌 수 있는 액수를 구해서 배열에 저장한다고 해봅시다. (이걸 해결하면 우리가 원하는 결과값은 X=1 입니다.) 이때 우리는 X+1 일부터 마지막일 까지 각각의 날짜부터 일을 시작했을때 가장 많이 벌 수 있는 액수를 이미 알고 있습니다.
이때 우리가 구하려고 하는 건, X일에 시작되는 상담을 한다 / 안한다 오로지 두가지 경우 입니다.
상담을 하는 경우, 구하려는 값은 "X일에 시작한 상담의 상담비" + "그 상담이 끝나는 다음날부터 일을 시작했을 때 가장 많이 벌 수 있는 액수" 가 됩니다.
상담을 하지 않는 경우, "X+1 일부터 시작했을 때 가장 많이 벌 수 있는 액수" 와 같습니다.

우리는 상담을 하는 경우와 하지 않는 경우 둘 중에 더 많이 벌 수 있는 케이스를 선택하면 됩니다.

이걸 마지막날부터 첫날까지 동일한 알고리즘으로 반복하면 첫날부터 마지막날 까지 각각의 날짜에 일을 시작했을 때 가장 많이 벌 수 있는 액수 배열이 모두 완성되게 됩니다! 이러한 방식으로 반복되는 연산을 획기적으로 줄일 수 있습니다. 물론 DP는 시간/공간 트레이드오프가 발생합니다.

파이썬 코드는 다음과 같습니다.

def solution(input) : 
    N = int(input())
    L = [0] # input 배열
    for i in range(N) :
        L.append(tuple(map(int, input().split())))
    best = [0]*(N+2) # best 에는 i 일자부터 일했을 때 가장 많이 벌 수 있는 액수가 저장된다.
    # 배열은 코드 편의성을 위해 index = 일자 로 사용하여 index 0 은 비운다. index out of bound 를 막기 위해 뒤에 하나 더 추가했다.

    for i in range(N,0,-1) : # 마지막날짜부터 best 를 채워간다.
        mon = best[i+1]
        fday = i + L[i][0] - 1
        if fday <= N :
            mon = max(mon, L[i][1] + best[fday+1]) # (i 일자 상담을 수락하지 않은 경우, i 일자 상담을 수락한 경우) 중 더 많이 버는 경우 찾기
        best[i] = mon
    print(best[1])
    


solution(input)