다음 표에서 T는 상담에 걸리는 시간(일)이고 P는 상담으로 버는 돈이다. 마지막날까지 하고 퇴사한다고 할 때 가장 많이 벌 수 있는 돈을 구하시오.
단 ,일은 0시 부터 시작한다. 즉, 마지막날 1짜리 일은 할 수 있는 것이다.
풀이
처음에는 dfs memoization으로 풀려했다. 하지만 시간초과와 recursion error가 발생하여 보니까 n의 범위가 150만이다. 그냥 풀이를 보았다.
풀이는 이렇다.
각 날짜에서 선택할 수 있는 방법은 두 가지이다. 그 날 배정된 상담을 하느냐 안하느냐. for문을 0부터 n-1까지 돌려서 각 step에서는 상담을 하는 경우를 다룬다. 예를들어 i = 0 일 때 첫 날 상담을 하는 경우를 다루고 상담을 안하는 경우는 i=1 이상에서 다뤄지는 것이다. dp table은 i일 까지 진행했을 때 최대로 벌 수 있는 돈의 양이다. 그리고 i일 까지중의 dp의 최대값 m이 설정된다.
일단 코드를 보자.
n = int(input())
t,p = [],[]
for _ in range(n):
x,y = map(int,input().split())
t.append(x)
p.append(y)
dp = [0]*(n+1)
m = 0
for i in range(n):
m = max(m,dp[i])
if i+t[i] > n:
continue
dp[i+t[i]] = max(dp[i+t[i]], m+p[i])
print(max(dp))
다음은 코드를 실행한 결과이다. 3일째 까지는 완료한 상담이 없으므로 dp가 0이다. 4일째에 받을 수 있는 max 돈은 10이다. 이는 1일 째 상담을 하거나 3일째 상담을 한 것이다. 그리고 4일쨰에 상담을 하면 5일째에 max돈은 30이 된다. 이런식으로 계속 진행한다.
m은 현재까지 진행된 날짜 중 dp의 최댓값을 의미한다. 즉, 가장 많이 돈을 번 경우에다가 현재날짜 상담을 한 경우를 계산하는 것이다.
dp = [0]*(n+1)dp table의 크기를 n+1로 설정함으로써 마지막날에 1일 걸리는 상담을 하는 경우를 깔끔하게 처리할 수 있게 됐다.
