[BOJ/백준] 14501번 퇴사 (Python 파이썬)

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

14501번: 퇴사

 

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
2 초	512 MB	67464	33777	21908	48.918%

문제

상담원으로 일하고 있는 백준이는 퇴사를 하려고 한다.

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

백준이는 비서에게 최대한 많은 상담을 잡으라고 부탁을 했고, 비서는 하루에 하나씩 서로 다른 사람의 상담을 잡아놓았다.

각각의 상담은 상담을 완료하는데 걸리는 기간 Ti와 상담을 했을 때 받을 수 있는 금액 Pi로 이루어져 있다.

N = 7인 경우에 다음과 같은 상담 일정표를 보자.

 1일2일3일4일5일6일7일TiPi

3	5	1	1	2	4	2
10	20	10	20	15	40	200

1일에 잡혀있는 상담은 총 3일이 걸리며, 상담했을 때 받을 수 있는 금액은 10이다. 5일에 잡혀있는 상담은 총 2일이 걸리며, 받을 수 있는 금액은 15이다.

상담을 하는데 필요한 기간은 1일보다 클 수 있기 때문에, 모든 상담을 할 수는 없다. 예를 들어서 1일에 상담을 하게 되면, 2일, 3일에 있는 상담은 할 수 없게 된다. 2일에 있는 상담을 하게 되면, 3, 4, 5, 6일에 잡혀있는 상담은 할 수 없다.

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

퇴사 전에 할 수 있는 상담의 최대 이익은 1일, 4일, 5일에 있는 상담을 하는 것이며, 이때의 이익은 10+20+15=45이다.

상담을 적절히 했을 때, 백준이가 얻을 수 있는 최대 수익을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N (1 ≤ N ≤ 15)이 주어진다.

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

출력

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

예제 입력 1

7
3 10
5 20
1 10
1 20
2 15
4 40
2 200

예제 출력 1 

45

예제 입력 2 

10
1 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10

예제 출력 2 

55

예제 입력 3 

10
5 10
5 9
5 8
5 7
5 6
5 10
5 9
5 8
5 7
5 6

예제 출력 3 

20

예제 입력 4 

10
5 50
4 40
3 30
2 20
1 10
1 10
2 20
3 30
4 40
5 50

예제 출력 4 

90

 

---

풀이

Dynamic Programming은 큰 문제를 작은 부분 문제로 나누고, 그 작은 부분문제들이 반복되는 것을 이용하여 풀어가는 방법입니다. 모든 작은 문제들을 단 한 번만 풀어야 하며, 그 결과를 어딘가 기록해 둠으로써 재사용합니다.

부분 문제를 푸는 순서에 따라서 Top-Down과 Bottom-up 으로 나뉩니다. DP의 가장 기본적인 문제인 만큼 두 가지 모두 작성해 보았습니다.

Bottom-up

부분 문제 풀이를 기록할 dp라는 리스트를 생성하였습니다. dp에는 i번째 일까지 일했을 때 얻을 수 있는 최대 수익이 담기게 됩니다. 따라서 최종적으로는 리스트의 가장 마지막 값을 출력하면 됩니다.

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에는 각 인덱스마다 [상담 기간, 비용]이 담기게 됩니다. 
이중 반복문을 살펴보면,

1. "i번째까지 일했을 때 얻는 최대 수익"을 계산하기 위한 i를 기준으로
2. j는 i번째 날에 상담을 진행했을 때, "상담이 가능한 모든 날짜", 즉 i + "상담 기간"부터 마지막 날까지 입니다.
3. 그리고, j를 기준으로 상담을 진행했었을 때 얻는 최대 수익을 dp[j]에 저장하도록 합니다.

이렇게 짜야만 모든 input case에 대해서 처리가 가능합니다.

만약 greedy하게 모든 상담 스케줄을 가능한 족족 채우게 되는 경우보다 며칠 상담을 안 하는 경우가 수익이 더 클 수 있기 때문입니다.

Top-Down

이번에는 위에서 부터 내려오겠습니다

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):
    # i일에 상담을 하는 것이 퇴사일을 넘기면 상담을 하지 않는다.
    if i + li[i][0] > N:
        dp[i] = dp[i+1]
    else:
        # i일에 상담을 하는 것과 상담을 안하는 것 중 큰 것을 선택
        dp[i] = max(dp[i+1], li[i][1] + dp[i + li[i][0]])

print(dp[0])

dp의 역할을 똑같으며, 방향만 역순으로 진행하면 됩니다.
if문이 길어지기 때문에 단순하게 max()를 이용하여서 i일에 상담을 하는 것과 상담을 안하는 것 중 큰 것을 선택하도록 했습니다.