문제
풀이
전형적인 dp 문제이다.
1일까지 밖에 없을 때의 최댓값
2일까지 밖에 없을 때의 최댓값
3일까지 밖에 없을 때의 최댓값
...
N일까지의 최댓값
이런식으로 계속 나아가다 보면 결국 총 주어진 일 수인 N일까지 얻을 수 있는 이익의 최댓값을 구할 수 있다.
문제 예시에 따라 순서대로 진행해보자.
n=7일 때의 상담 일정표이다.
여기서 T는 상담 소요시간, P는 상담 진행 후 이익을 의미한다.
먼저 dp 테이블은 n+1 크기로 생성해 모두 0으로 초기화한다. n+1 크기로 만드는 이유는 이미 인덱스값과 상담 일자를 일치시켜주기 위함이다.
이제 1일차에서 n일차까지의 최대이익을 순서대로 구해보자.
1일차
1일차에는 애초에 1일차 상담 하나밖에 없으므로 별도의 고려사항이 없는데, 해당 상담 조차 3일의 시간이 소요되기 때문에 사실상 1일차에 얻을 수 있는 이익은 0이다. 다만 상담을 진행한다면 3일차가 되었을 때의 최대 이익이 10이 될 가능성이 생기므로 dp 테이블은 아래와 같이 업데이트 된다.
dp = [0,0,0,10,0,0,0,0]
2일차
2일차의 최대이익 역시 0이다. 1일차 상담과 2일차 상담 모두 현재 날짜까지 끝낼 수 있는 상담이 없기 때문이다. 따라서 dp는 1일차와 같은 논리로 아래와 같이 업데이트된다.
dp =[0,0,0,10,0,0,20,0]
3일차
3일차의 최대이익은 10이다. 이는 3일차가 되었기 때문에 3일이 소요되었던 1일차의 상담의 최대이익 일수도 있고(이는 알다시피 이미 dp 테이블에 업데이트 되어있다) 3일차 상담일 수도 있다.
무엇을 선택했는지는 고려대상이 아니므로 신경쓸 필요가 없으며, 우리는 결국 dp의 궁극적인 목적인 점화식을 찾아야하기에 이를 주의깊게 관찰하기만 하면 된다.🙃
dp =[0,0,0,10,0,0,20,0]
4일차
4일차의 최대이익은 30이다. 왜냐하면 3일차까지 얻을 수 있는 최대 이익 10과 4일차 상담이 하루만에 20 이익을 벌어다주기 때문이다.
dp =[0,0,0,10,30(=10+20),0,20,0]
5일차 & 6일차
5일차의 최대이익은 여전히 30이다. 왜냐하면 5일차 상담은 이틀이 소요되어 추가로 이익을 얻을 수 없기 때문이다. 따라서 4일차의 최대이익과 동일하다. 대신 상담을 진행한다면 6일차가 되었을 때의 이익을 15만큼 더해줄 수 있으므로 dp 테이블은 아래와 같이 업데이트 된다.
dp =[0,0,0,10,30,30,45(=30+15),0]
여기서 생각해볼 점은 5일차 이전까지 6일차의 최대이익은 20이었으나, 5일차가 되는 시점에서는 5일차의 최대 이익 30 + 6일차에 비로소 취할 수 있는 이익인 15가 더해져 45의 이익을 얻을 수 있기 때문에 max(20,45)=45로 6일차의 최대이익이 업데이트 되었음을 알 수 있다.
이를 잘 살펴보면, 현재 날짜를 n이라고 했을 때
dp[n]=max(dp[n],dp[n-1]) 을 수행한 후,
현재 날짜에 진행되는 상담의 끝나는 날짜(❗️당일 포함❗️)를 고려하여 해당 날짜에도 아래의 점화식을 통해 이익을 업데이트 해준다.
dp[n+t-1]=max(dp[n+t-1],dp[n-1]+p)
(여기서 의미하는 dp[n-1]+p가 위에서 볼드처리한 부분을 의미한다)
다만, 끝나는 날짜가 우리가 찾고자 하는 최종날짜보다 넘어서지 않도록 조건 처리를 해주어야 한다.
import sys
input = sys.stdin.readline
n = int(input())
arr = []
arr.append((0, 0))
for _ in range(n):
arr.append(tuple(map(int, input().split())))
dp = [0] * (n + 1)
for i in range(1, n + 1):
t, p = arr[i]
dp[i] = max(dp[i], dp[i - 1])
fin_date = i + t - 1
if fin_date <= n:
dp[fin_date] = max(dp[fin_date], dp[i - 1] + p)
print(dp[n])
