[백준 - Python] 14501. 퇴사 (DP)

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

14501번: 퇴사

 

문제

오늘부터 N+1일째 되는 날 퇴사하기 위해, N일 동안 최대한 많은 상담을 하려고 한다.

상담을 완료하는데 걸리는 기간 Ti,

상담을 했을 때 받을 수 있는 금액 Pi를 입력 받는다

 

N=7인 경우의 상담 일정표이다.

 

위 상담 일정표에 따르면,

1일에 상담을 하게 되면, 2일과 3일에 있는 상담은 할 수 없고

2일에 상담을 하게 되면 3, 4, 5, 6에 있는 상담은 할 수 없다

 

또한, N+1일째에는 회사에 없기 때문에 6, 7일에 있는 상담은 할 수 없다

 

퇴사 전에 할 수 있는 상담의 최대 이익은 1일, 4일, 5일에 있는 상담을 하는 것이며,

이때의 이익은 10 + 20 + 15 = 45 이다.

 

상담을 적절히 하여, 최대 수익을 구해야 한다.

 

 

문제 풀이

DP를 이용해 해결할 수 있는 문제이다.

 

1. 보텀업 방식

import sys
N = int(input())
schedule = [list(map(int, sys.stdin.readline().split())) for i in range(N)]

dp = [0 for i in range(N+1)]

for i in range(N):
    for j in range(i + schedule[i][0], N+1):
        if dp[j] < dp[i] + schedule[i][1]:
            dp[j] = dp[i] + schedule[i][1]

print(dp[-1])

 

schedule 변수에는 [상담 기간, 비용]이 담기게 된다

dp 리스트는 i번째 일까지 일했을 때 얻을 수 있는 최대 수익이 담긴다.

따라서 마지막에 결과값으로 리스트의 가장 마지막 값을 출력하면 된다.

 

이중 반복문에서

i 반복자는 i번째까지 일했을 때 얻는 최대 수익을 계산하기 위함이고

j 반복자는 i번째 날에 상담을 진행했을 때, "상담이 가능한 모든 날짜"를 돈다.

 

j를 기준으로 상담을 진행했었을 때 얻는 최대 수익을 dp[j]에 저장을 하는데

이때, dp[j] 에 저장되어 있는 값이 dp[i]에 저장되어 있는 값에 i일 비용을 더한 값보다 작으면

해당 값으로 갱신해준다.

 

 

2. 탑다운 방식

N = int(input())
li = [list(map(int, input().split())) for _ in range(N)]
dp = [0 for _ in range(N+1)]

for i in range(N-1, -1, -1):
    if i + li[i][0] > N:
        dp[i] = dp[i+1]
    else:
        dp[i] = max(li[i][1] + dp[i + li[i][0]], dp[i+1])

print(dp[0])

 

dp의 역할은 똑같고 dp 리스트 갱신 방향만 역순으로 진행된다.

 

문제에서 N+1일 째에는 회사가 없기 때문에 상담 진행이 불가능하다고 했으므로

i일에 상담을 하는 것이 퇴사일을 넘기면, 상담을 하지 않는다.

 

i일에 상담을 하는 것과 i일에 상담을 하지 않는 것 중 큰 것을 선택한다.

 

 

참고 자료

https://great-park.tistory.com/48