[Python] 백준 14501번 퇴사(DP)

문제

풀이

DP문제이다.

먼저 생각해볼 조건은 "이 날(i)의 상담을 받으면 T[i]의 날짜 만큼 상담을 받지 못한다."이다.

그렇기에 한 날짜에서 어느 값이 가장 큰 지를 비교하려면 단순히 생각해서 전 날들의 상태 들을 하나 하나 비교해야 한다는 단점이 있다.

예를 들어 3일에서 최댓값을 비교하려면 "2일을 선택하거나(2일의 T가 5일 이기 때문) 1일을 선택하거나(1일의 T가 3일 이기 때문) 혹은 자신을 선택 해야 한다."이다. 따라서 인덱스 값이 올라갈 수록 더욱 많은 연산을 필요로 한다.(이미 DP가 아니다.)

하지만 이것을 뒤집어 생각한다면 쉬워진다.

일단 하나의 인덱스에서는 두 가지 선택지가 있다.

"현재의 일을 받아들이고 현재의 일이 끝나는 시점에 일들을 받아들이는 쪽이 이득이다."

"현재의 일을 받아들이면 못 수행하는 일들을 받아들이는 쪽이 이득이다."

먼저 7일부터 생각하여 만약 (T + 현재 일수)가 최대 일수를 넘긴다면 pass한다.(7일은 7+T(2일))

넘기지 않는다면 현재 일수의 값(P[i])과 현재 일수를 끝낸 다음(T[i])할 수 있는 일들(쌓아온 cache[i+T[i]])을 더하는 값이 첫 번째

cache[i+t[i]]+p[i]

예) 5일의 P(값은 15)+ 5일+T(값은 2일)일에서 쌓아온 값(5+T는 7 이니까 7일에서 쌓아온 값, 물론 0임)

두 번째는 현재의 일을 포기하고 그저 쌓아온 값을 가져오는 것

cache[i+1]

이 둘을 비교하여 가장 큰 값을 쌓아 주면 된다.

물론 퇴사를 하기로 한 날짜를 넘기는 상담이면 그냥 시도조차 못하기 때문에 cache[i+1]의 선택지 밖에 없을 것이다.

N = int(input())

arr = []

for _ in range(N):

    arr.append(list(map(int, input().split())))

cache = [0 for _ in range(N+1)]

for i in range(N-1, -1, -1):

    t, p = arr[i]

    if t+i > N:

        cache[i] = cache[i+1]

        continue

    cache[i] = max(cache[i+t]+p, cache[i+1])

print(cache[0])