14501번 - 퇴사*

동적계획법 (DP : Dynamic Programming)
큰 문제를 작은 문제로 나눠서 푸는 알고리즘
수행시간의 비약적 향상이 핵심으로 '메모이제이션'이라는 기법을 사용해 이미 계산된 결과는 별도의 메모리에 저장하여 필요한 경우 다시 계산하지 않고 다시 꺼내 사용하는 방식

• Top-Down 방식 : 메모이제이션을 통한 재귀함수를 사용한 방식
• Bottom-Up 방식 : 결과 저장용 리스트인 dp 테이블을 통해 반복문으로 문제를 해결

N = int(input())
T = []
P = []
dp = []
for _ in range(N):
    t, p = map(int, input().split())
    T.append(t)
    P.append(p)
    dp.append(p)
    
dp.append(0)

for i in range(N-1,-1,-1):
    if (T[i]-1)+(i+1) > N:
        # 아무것도 하지 않고, 이전 값(dp[i+1]) 그대로 가져옴
        dp[i] = dp[i+1]
    else:
        # 기존 상담 스케쥴(dp[i+1])과 현재 상담을 새로 가져온 스케쥴(P[i] + dp[i+T[i]]) 중에서 큰 값
        dp[i] = max(dp[i+1], P[i] + dp[i + T[i]])

print(dp[0])

 

* 뒤에서 부터 확인하면서 DP를 갱신한다. -> 상담날이 퇴사날을 초과하는 경우 기존 상담 스케쥴 유지

* 새로운 상담이 가능한 경우, 기존의 상담 스케쥴과 현재 상담+겹치지 않는 이전 상담 스케쥴 중에서 큰 값을 가져옴