[백준] 14501. 퇴사 (python)

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

14501번: 퇴사

 

문제

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

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

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

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

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

 

	1일	2일	3일	4일	5일	6일	7일
Ti	3	5	1	1	2	4	2
Pi	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

 

 

풀이

최종 해는 N일째 동안 얻을 수 있는 최대 수익이고, i일째 얻을 수 있는 최대 수익(부분 해)을 N번째까지 구하면 최종 해를 구할 수 있기 때문에 다이나믹 프로그래밍을 이용하는 문제이다. 

 

다이나믹 프로그래밍은 부분 해를 구해나가는 방향에 따라 크게 두 종류로 나눌 수 있는데, 보텀업 방식과 탑다운 방식이다. 이 문제도 두 가지 방식으로 풀 수 있다.

 

Bottom-Up 방식

1일째부터 N일째까지 올라가면서 각 날짜에서 벌 수 있는 최대 수익을 계산한다.

dp [i]는 i일에 벌 수 있는 최대 수익을 의미한다.

그리고 수익을 버는 날짜는 상담이 끝난 다음날이다.

그럼 위 예시에서 1일에는 상담이 끝나지 않아 돈을 벌 수 없고, 상담이 끝나고 다음 날이 4일째에 돈을 받게 된다.

이 방식의 점화식은 다음과 같다.

i가 상담을 시작하는 날이고, j가 상담 이후 날짜라면

$$ dp[j] = max(d [i + t [i]], d [j]) $$

위와 같이 상담이 끝난 이후의 수익에 대해서 구한다.

 

n = int(input())
arr = []
for _ in range(n):
    t, p = map(int, input().split())
    arr.append([t,p])

d = [0] * (n+1)

for i in range(n):
    for j in range(i + arr[i][0], n+1):
        d[j] = max(d[j], d[i]+arr[i][1])

print(d[n])

 

 

Top-Down 방식

반대로 마지막 날부터 첫째날까지 내려오면서 구하는 방식이 있다.

여기서 

dp[i]는 i번째 날 이후로 벌 수 있는 최대 수익을 의미한다.

예를 들면 위 예시에서 dp [7]은 7번째 날 이후로 벌 수 있는 수익인데, 8일째부터는 회사를 나오지 않으므로 0이다.

dp [5] 은 5번째 날 이후로 벌 수 있는 수익인데, 5번째 날에 15를 벌 수 있고, 해당 상담(2일 걸림) 이후 7번째 날 벌 수 있는 최대 수익은 0이므로 15이다.

dp [4]은 4번째 날 이후로 벌 수 있는 수익인데, 4번째 날에 20을 벌고, 해당 상담(1일 걸림) 이후 5번째 날부터 벌 수 있는 최대 수익은 15이므로 dp [4]는 20 + 15 = 35이다.

dp [3]은 3번째 날 이후로 벌 수 있는 수익인데, 3번째 날에 10을 벌고, 해당 상담(1일 걸림) 이후 4번째 날부터 벌 수 있는 최대 수익은 35이므로 dp [3]은 35 + 10 = 45이다.

 

이때, 해당 날짜에 벌 수 있는 수익과 그 날짜 이후에 버는 최대 수익을 더해야 하기 때문에,

마지막날부터 내려오면서 벌었던 최대 수익의 값을 저장해둔다.

이 방식의 점화식은 다음과 같다.

$$ dp [i] = max(p[i] + d[i + t[i]], max_value) $$ 

여기서 

$$ dp[i] = p[i] + d [i+t [i]] $$

를 하지 않고 max_value와 비교해 주는 이유는 '해당 날짜의 수익과 해당 상담이 끝난 이후의 최대 수익을 더한 값'이 꼭 최대 수익임을 보장할 수 없기 때문이다.

왜냐하면 "해당 날짜의 수익 + 해당 상담 끝난 이후 최대 수익"이라는 말은 해당 날짜의 상담을 하기로 선택했다는 의미인데, 그 말은 해당 상담이 끝나기 전까지의 모든 상담을 선택하지 않았다는 말과 같다.

하지만 경우에 따라서 선택하지 않은 상담의 수익이 더 클 수도 있다. 이 경우를 위해서 i번째 날 이후 벌 수 있는 최대 수익을 max_value에 담아서 저장하고, 그 값과 비교해 주는 것이다.

 

1. p [i] + d [i+t [i]]  = "해당 날짜의 수익 + 해당 상담 끝난 이후 최대 수익"

2. max_value = 해당 날짜 이후 벌 수 있는 최대 수익

 

만약 1번 값이 더 크다면 dp [i]는 1번 값으로 갱신하지만, 1번을 계산해 봤는데, 1번을 선택하지 않았을 때 발생할 수 있는 최대 수익인 max_value가 더 크다면 해당 상담을 선택하지 않고, 2번으로 갱신하는 것이 맞다.

 

n = int(input())
arr = []
for _ in range(n):
    t, p = map(int, input().split())
    arr.append([t,p])

d = [0] * (n+1)

max_value = 0
for i in range(n-1, -1, -1):        # 0 ~ (n-1) 까지의 값이 있으므로 => n-1 , n-2, ... , 2, 1, 0 까지
    time = arr[i][0] + i
    # d[i] = i번째 날부터 마지막 날까지 낼 수 있는 최대 이익
    if time > n:
        d[i] = max_value
        continue
    d[i] = max(max_value, arr[i][1] + d[time])
    max_value = d[i]

print(max_value)

 

 

회고

사실 이 문제는 스스로 풀지 못했고, 다른 답안을 참고해서 정리했다.

다이나믹 프로그래밍 알고리즘 자체를 좋아하는 편인데, 이 유형의 문제는 너무 어려운 것 같다...

dp테이블을 저장하는 의미를 어떻게 정의하느냐에 따라서, 

그리고 탑다운 방식, 보텀업 방식 등 어떻게 풀이하느냐에 따라서,

문제풀이가 다양하기 때문에 한 문제를 소화하는 게 더욱 오래 걸린다.

 

사실 해당 유형 문제를 많이 접하면서

dp의 의미를 어떻게 정의할지, 어떤 방식으로 풀지 등을 빠르게 선택해

최적의 해까지 도달해 내는 과정을 계속 연습하는 수 밖에는 없을 것 같다.

대신 문제를 풀었다고 넘어가지 말고, 다양한 방법의 풀이를 보면서 

어떻게 푸는 게 더 좋을지, 왜 이렇게 풀었는지, 등등에 대해서 충분히 생각하고 넘어가면 좋을 것 같다.