[#14501] 퇴사

RookieAND·2022년 4월 24일

DP 백준 코테

BaekJoon

목록 보기

5/42

❓ Question

📖 Before Start

이번에도 동적 프로그래밍 이지만.. 점화식 자체를 좀처럼 세우지 못하였다.

이번 문제도 나에게는 너무나 어려운 동적 프로그래밍이다. 20분 간의 고민을 하며 이것저것 프로그램을 설계하였으나 결국 시간 초과로 인해 힌트의 도움을 받아야만 했던 문제였다.
하지만 막상 답안을 보니 "왜 이런 간단한 걸 생각하지 못했을까?" 싶은 녀석이었다. 정말.. DP는 많이 풀어도 늘 새롭게 느껴진다.

✒️ Design Algorithm

1일차부터 순차적으로, 해당 상담을 끝낸 날에 수익을 추가해주면 되지 않을까?

따라서 나는 단순하게 N일차 상담을 마치기 위해서 X일이 소요된다면, N+X 일에 얻을 수 있는 추정 수익에 N일에 진행한 상담의 수익을 더해주는 식으로 먼저 접근하였다.

아래는 필자가 문제를 풀기 전 작성한 알고리즘 설계이다.

N일 차에 진행한 상담에 대한 수익을 구하여 누적합으로 최댓값을 유도한다.

N일차 에 얻을 수 있는 누적 수익 정보를 메모이제이션에 저장한다.
N일 차에 진행한 상담에 대한 정보를 tuple 로 묶어 list 에 저장한다.
이후 1일차 부터 N일차 에 대한 상담 정보를 for 반복문을 통해 순차적으로 불러온다.
만약 N일차 상담에 필요한 시간이 A, 수익이 B라면, N+A일 의 추정 수익에 b 를 더한다.

💻 Making Own Code

❌ Wrong Code

import sys

n = int(sys.stdin.readline())
consult = [tuple(map(int, sys.stdin.readline().split())) for _ in range(n)]
dp = [0] * (n)

for i in range(n):
    time, cost = consult[i]
    if time + i > n:
        dp[i] += cost + dp[i + time]
print(dp[n-1])

시도는 좋았으나 결론적으로는 완전히 잘못된 문제 접근 방식이었다.

호기롭게 식을 짜긴 했지만, 막상 식을 짜는 과정에서도 나의 의문점들은 좀처럼 풀리지 않았다.
만약 1일차에 상담을 진행했는데, 1일차를 무시하고 2일차에 상담을 진행하는 것이 더 이득이라면?
이런 문제 덕에, 순차적으로 하나씩 상담을 조회하는 방식으로는 문제 해결이 좀처럼 쉽지 않았다.

✅ Correct Code

import sys

n = int(sys.stdin.readline())
consult = [tuple(map(int, sys.stdin.readline().split())) for _ in range(n)]
dp = [0] * (n+1)

for i in range(n-1, -1, -1):
    time, cost = consult[i]
    if time + i > n:
        dp[i] = dp[i+1]
    else:
        dp[i] = max(cost + dp[i + time], dp[i + 1])
print(dp[0])

결국 이번 문제는 힌트의 도움을 받았다. 다른 분의 풀이에서는 아래와 같이 문제를 접근하였다.

역으로 7일부터 1일까지의 상담 정보를 읽어 점화식을 구현하면 된다.

우선 time + i > n 조건식으로 종료 일자가 퇴사일 이후인 경우, 해당 일자의 상담을 진행할 수 없으므로 이전 일수의 상담 수익을 그대로 가져온다.
만약 해당 일자의 상담을 진행할 수 있다면, 상담을 마친 후의 일자에 모인 추정 수익에 해당 상담의 수익을 더한 금액이 더 큰지, 아니면 상담을 넘긴 다음 날의 추정 수익이 더 큰지를 구하면 된다.

만약 아래와 같은 케이스가 있다면, 그에 따른 dp[i] 의 값은 표의 최하단과 동일하다.

	i=1	i=2	i=3	i=4	i=5	i=6	i=7
시간	3	5	1	1	2	4	2
수익	10	20	10	20	15	40	200
dp[i]	45	45	45	35	15	0	0

i=7인 경우, 7 + 2 = 9 이므로 해당 일자의 상담은 퇴사일 이후에 끝낼 수 있다. 따라서 상담은 불가능하며 추정 수익은 그대로 0원이다. 6일차의 상담도 같은 이유로 진행이 불가능한 케이스다.

i=5 인 경우, 5 + 2 = 7 이므로 진행이 가능한 상담이다. 현재 5일차의 상담을 진행할 경우
들어오는 보상은 cost + dp[7] 이 된다.
하지만 이 상담을 진행하지 않을 경우에는 추정 수익이 dp[6] 이 된다. 따라서 값이 더 큰
cost + dp[7]가 dp[5] 에 들어오는 값이 된다.