백준 14501) 퇴사_ Python

문제 

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

14501번: 퇴사

 

코드

import sys

input = sys.stdin.readline

N = int(input())
T = [0]*(N+1)
P = [0]*(N+1)
for i in range(N):
    Ti, Pi = map(int, input().split())
    T[i] = Ti
    P[i] = Pi

DP = [0]*(N+1)
for i in range(N-1, -1, -1):
    if(N-i < T[i]):
        DP[i] = DP[i+1]  # 주어진 시간안에 상담할 수 없음, 이전 값과 동일
    else:
        DP[i] = max(DP[i+1], P[i]+DP[i+T[i]])  # 이전 값 vs 이번 상담 + 이전 상담

print(DP[0])

 

 

문제 풀이 과정

• Knapsack하고 비슷하게 생각하면 되는 문제로, DP로 푼 문제이다.
• 이 문제는 DP를 뒤에서부터 시작하면 반복문을 한번에 끝낼 수 있다.
• 점화식을 세워보자.
  • 6,7일 같은 예시는 6일 부터 시작해서 4일짜리 상담, 7일부터 시작해서 2일짜리 상담이므로 불가능하다. 따라서 해당 날짜+상담에 걸리는 시간이 퇴사날보다 뒤면 해당 날짜는 선택하지 못한다.
    • if(N-i < T[i]): DP[i] = DP[i+1]
  • 그리고 만약 해당 날짜에 상담을 할 수 있다고 하면, 이때 value를 따져야 한다. 5일의 값을 정한다고 고려해보자.
    • 해당 날짜에는 상담을 안하는 경우
      • 이전 경우까지의 값 선택
        • DP[i]=DP[i+1]
        • 6일 상담까지의 최댓값 (거꾸로 센다!)
    • 해당 날짜에 상담을 하는 경우
      • 이전 경우까지의 값 vs 해당 날짜에 받을 수 있는 값 + (해당 날짜+상담 걸리는 기간) 날짜의 값
        • DP[i]= P[i]+DP[i+T[i]])
        • 6일까지 값vs 5일분 + 7일(5일 상담은 이틀 걸리므로) 까지의 값
    • 이 두가지중 더 많은 돈을 벌 수 있는 경우를 선택하면 된다.