[DP] 이코테 “퇴사” Python 풀이

문제

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

• 오늘부터 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)

출력 조건

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

입력 예시

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

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

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

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

출력 예시

45

55

20

90

풀이

• 아래 예제에서, 1일차에 상담을 진행한다고 해보자.

        1일    2일    3일    4일    5일    6일    7일
    Ti     3     5     1     1     2     4      2
    Pi    10    20    10    20    15    40    200

• 이 경우 3일에 걸쳐서 상담을 진행해야 한다.

• 결과적으로 4일부터 다시 상담을 진행할 수 있다.

• 그러므로 1일 차에 상담을 진행하는 경우의 최대 이익은,

• ‘1일 차의 상담 금액 + 4일부터의 최대 상담 금액’이 된다.

• 이러한 원리를 이용하여 뒤쪽 날짜부터 거꾸로 계산하며 문제를 해결할 수 있다.

• 뒤쪽부터 매 상담에 대하여 ‘현재 상담 일자의 이윤(p[i]) + 현재 상담을 마친 일자부터의 최대 이윤(dp[t[i] + i]])’을 계산하면 된다.

• 이후에 계산된 각각의 값 중에서 최댓값을 출력하면 된다.

• dp[i]가 i번째 날부터 마지막 날까지 낼 수 있는 최대 이익이라고 한다면, 점화식은 아래와 같다.

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

• 이때 max_value는 뒤에서부터 계산할 때, 현재까지의 최대 상담 금액에 해당하는 변수이다.

예제 코드

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

import sys

# 전체 상담 개수
n = int(sys.stdin.readline())

t = [] # 각 상담을 완료하는데 걸리는 기간
p = [] # 각 상담을 완료했을 때 받을 수 있는 금액

dp = [0] * (n + 1) # i번째 날부터 마지막 날까지 낼 수 있는 최대 이익

max_value = 0

for _ in range(n):
    x, y = map(int, sys.stdin.readline().split())
    t.append(x)
    p.append(y)

# 리스트를 뒤에서부터 거꾸로 확인
for i in range(n-1, -1, -1):

    # i번째 날짜에 상담이 가능한 경우
    if (i + t[i] <= n):
        # (현재 상담 날짜의 금액 + 다음 상담 날짜의 누적 금액)과
        # 현재 상담 날짜부터 마지막 날까지 쌓을 수 있는 최대 누적 금액을 비교
        dp[i] = max(p[i] + dp[i+t[i]], max_value)
        max_value = dp[i]
    # i번째 날짜에 상담이 불가능한 경우
    else:
        dp[i] = max_value

print(max_value)

참고

• 이것이 취업을 위한 코딩 테스트다. with python