[이코테] 다이나믹 프로그래밍 - 퇴사

문제 <퇴사>

상담원으로 일하고 있는 백준이는 퇴사를 하려고 한다. 오늘부터 N+1일째 되는 날 퇴사를 하기 위해서, 남은 N일 동안 최대한 많은 상담을 하려고 한다.백준이는 비서에게 최대한 많은 상담을 잡으라고 부탁을 했고, 비서는 하루에 하나씩 서로 다른 사람의 상담을 잡아놓았다.

각각의 상담은 상담을 완료하는데 걸리는 기간 Ti와 상담을 했을 때 받을 수 있는 금액 Pi로 이루어져 있다. 상담을 적절히 했을 때, 백준이가 얻을 수 있는 최대 수익을 구하는 프로그램을 작성하시오.

---

입력

• 첫째 줄에 N (1 ≤ N ≤ 15)이 주어진다.
• 둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 5, 1 ≤ Pi ≤ 1,000)

---

출력

• 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다.

---

풀이

• 상담 날짜를 뒤에서부터 선택하여 문제를 해결해야겠다는 생각을 했다.
• 처음에는 반복되는 작업을 재귀 함수를 이용하여 구현을 해보려 코드를 작성했다.

import sys

input_data = sys.stdin.readline

N = int(input_data())
consult = []
for i in range(N):
    t, p = map(int, input_data().split())
    consult.append((t, p))

_max = 0


def max_profit(d, k, p):
    left = k - consult[d][0]
    p += consult[d][1]
    for j in range(d-1, -1, -1):
        if consult[j][0] <= left and consult[j][0] + j <= d:
            p, left = max_profit(j, left, p)
    return p, left


for i in range(N-1, -1, -1):
    if consult[i][0] + i <= N:
        _max = max(_max, max_profit(i, N, 0)[0])
print(_max)

• 재귀 함수를 이용하여 문제를 풀었지만 원하는 답이 나오지 않았고, 함수의 반환값 설정이 명확하게 이루어지지 않았다.
• 또한 책에서는 재귀 함수를 통해 문제를 해결하는 것이 효율적이지 않을 수 있고, 시스템상 재귀 함수의 스택 크기가 한정되어 있어 리스트를 이용하는 것을 권장했다.
• 리스트를 이용하여 다이나믹 프로그래밍을 적용하면 다음과 같다.

import sys

input_data = sys.stdin.readline

N = int(input_data())
T, P = [], []
for i in range(N):
    t, p = map(int, input_data().split())
    T.append(t)
    P.append(p)

dp = [0] * (N+1)        # dp[i]는 i번째 날까지 일을 했을 때 최대 수익

for i in range(N-1, -1, -1):
    if i + T[i] <= N:       # 해당 일을 수행할 때 날짜를 초과하지 않을 경우
        dp[i] = max(dp[i + 1], P[i] + dp[i + T[i]])     # 오늘 상담 안 하는 경우, 오늘 상담 하는 경우
    else:                   # 날짜를 초과할 경우
        dp[i] = dp[i + 1]   # 다음날 값 가져옴

print(dp[0])

dp를 사용하는 것이 익숙하지 않아 다이나믹 프로그래밍을 적용하는 문제라는 것을 알고 있었지만 문제 해결에 어려움을 겪었다.

대부분의 다이나믹 프로그래밍 문제는 비슷한 형태로 구현되어, 원리를 명확하게 이해하여 문제를 푸는 노력이 필요하다!

---

 

 

 

 

 

14501번: 퇴사