[백준 14501번] 퇴사 (Python)

다이나믹 프로그래밍을 활용하여 푸는 문제이다. (DP? 나에겐 너 무 어 려 워 😭)

점화식 세우는게 반복되는 규칙성있는 로직을 파악하지 않고서야 감도 안잡히기 때문에

자꾸 DP문제에 그리디로 접근하게 되는 부족함이 있다.

하다하다 안되어서 뤼튼과 함께했다. → 이해를 목표로 다시 정리!

 

문제 링크

14501번 퇴사

(똑같은 문제, 15486번 퇴사2)

 

문제 요약

재택 근무 중인 백준이가 퇴사까지 남은 N일 안에 상담을 통해 얻을 수 있는 최대 수익을 계산하는 문제

상담을 완료하는 데 필요한 기간 ( T_i )와 상담을 통해 얻을 수 있는 수익 ( P_i )가 주어진다.

상담 기간이 퇴사일을 넘기면 안 되고, 한 번에 한 개의 상담만 진행할 수 있다.

 

필요 항목 정리

• 퇴사까지 N일

날짜별로 얻을 수 있는 최대 수익을 계산한다.

dp[i]를 i일부터 시작하는 상담을 통해 얻을 수 있는 최대 수익이라고 할 때,

dp[i] = max(dp[i + T[i] + P[i], dp[i+1]]로 점화식을 세울 수 있다.

i + T[i]는 i일에 상담을 시작할 경우 상담이 끝나는 날의 최대 수익에 현재 상담 수익을 더한 것이다.

dp[i+1]은 상담을 하지 않을 경우의 수익으로 다음날의 수익과 동일하다.

퇴사까지 남은 날짜부터 거꾸로 상담을 선택해 나가면서 최대 수익을 계산한다.

 

흐름을 글로 적어보면

뒤에서부터 확인하는 방법으로

• i : 7일 지난 시점 + t[i]: 주어진 일에 필요한 시간을 더한 값이
  • 퇴사 후라면 저장되어있던 최대 값으로 기록
  • 퇴사일 내라면 저장되어있던 값과, 상담 날짜에 이익과 이후에 벌 수 있는 값과 최댓값 중 큰 것으로 기록

n = int(input())
t, p = [], []
dp = [0] * (n + 1)
max_value = 0

for _ in range(n):
	x, y = map(int, input().split())
	t.append(x)
	p.append(y)

for i in range(n - 1, -1, -1): # 뒤에서부터 확인
	time = t[i] + i
	if time <= n: # 상담이 퇴사일 안에 끝나는 경우
		dp[i] = max(p[i] + dp[time], max_value)
		max_value = dp[i]
	else: # 상담이 퇴사일을 넘기는 경우
		dp[i] = max_value

print(max_value)

# t [3, 5, 1, 1, 2, 4, 2]
# p [10, 20, 10, 20, 15, 40, 200]
# dp [45, 45, 45, 35, 15, 0, 0, 0]