[백준] 14501. 퇴사/Python - Silver3

❓문제

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

성능 요약

메모리: 32412 KB, 시간: 36 ms

문제 설명

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

오늘부터 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이다.

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

✍🏻풀이

오늘날짜로부터 t만큼 더한 날에 수익이 얼마인지 계산한다.

예제에 나온 테스트케이스 4로 설명하겠다.

	1일	2일	3일	4일	5일	6일	7일	8일	9일	10일
Ti	5	4	3	2	1	1	2	3	4	5
Pi	50	40	30	20	10	10	20	30	40	50

오늘이 1일이라면 수익을 6일에 기록한다. 인덱스로 보면 dp[5]에 수익을 기록하면 된다. 2일, 3일, 4일, 5일에 T를 더하면 모두 6일에 상담이 완료된다. 그러므로 이때 기존 dp[5]의 값과 비교하여 최댓값을 기록하면 된다.

이제 6일은 상담이 완료되는데 1일이 걸리므로 7일에 수익을 기록한다. dp[6]은 dp[5]+10으로 60이 7일 최대 수익이다. 7일에 하는 상담은 2일이 걸린다. 그러므로 dp[8]에 기록한다. dp[8]은 80이 된다. 이제 9일을 보면 상담이 완료되는데 4일이 걸린다. 그런데 백준이는 11일에 퇴사하므로 상담을 완료할 수 없다. 그러므로 9일 상담은 잡지 않는다.

다시 8일로 돌아가서 8일에 상담을 잡으면 완료하는 데 3일이 걸린다. 그러므로 8일에 잡은 상담은 퇴사 전에 완료할 수 있다. 그럼 dp[10]은 dp[7]+30이 된다. 그런데 위 과정대로만 하면 현재 dp[7]은 수익이 0으로 되어있다. 그러므로 dp[i]와 dp[i-1]을 비교하여 최대 수익을 구하면 된다. 그러면 dp[7]은 dp[6]과 비교했을 때 dp[6]은 60으로 dp[7]은 60이 되고 dp[10]은 dp[7]+30으로 90이 되어 결과적으로 최대 수익은 90이다.

💻코드

import sys

input = sys.stdin.readline

N = int(input())
coun = [list(map(int, input().split())) for _ in range(N)]
dp=[0]*(N+1)
for i in range(N):
    t, p = coun[i]
    dp[i] = max(dp[i], dp[i - 1]) # i와 i-1을 비교하여 최대 수익을 계산.
    if i+t <= N: # 상담 완료일이 퇴사일을 넘기지 않는다면
        dp[i+t] = max(dp[i+t], dp[i]+p) # 상담 완료일에 받을 수 있는 최대 수익 계산.

print(max(dp))

📍후기

처음에는 DFS로 접근했는데 생각하다보니 DP로 풀 수 있을 것 같다고 생각했다. 일단 그렇게 생각하고 풀어서 맞긴 했지만 이렇게 풀어도 괜찮은건가 싶었는데 분류보니까 DP라고 되어있어서 잘못 접근한 건 아닌 것 같다ㅎㅎ

PyPy3로 하면 메모리를 상당히 먹는데 이게 맞는걸까...