실4
dp 문제이다.
Ti 는 내가 상담을 할 수 없는 날짜이므로, (상담에 걸리는 날짜)
뒤에서부터 내가 얻을 수 있는 이득을 쌓아가야 한다.
해당 문제에서 주어진 예시를 가져와서
| 1일 | 2일 | 3일 | 4일 | 5일 | 6일 | 7일 | |
|---|---|---|---|---|---|---|---|
| Ti | 3 | 5 | 1 | 1 | 2 | 4 | 2 |
| Pi | 10 | 20 | 10 | 20 | 15 | 40 | 200 |
예를 들어 내가 7일만 상담을 하려고 한다면, 불가능하다.
왜냐하면 7일에 상담을 시작하면 2일이 소요되기 때문에, 하루만에 끝낼 수 있는 상담이 아니라면 불가능하다.
그렇기 때문에 7일에 선택되는 상담은 1일 경우에만 시행 할 수 있다.
해당 날짜에 실행했을 때 상담을 할 수 있는 최대 수익값을 저장해줄 ans 라는 배열을 만들어주고, 7일에 0을 저장하게 된다.
6일 또한 불가능하다. 그러므로 0이 저장되게 된다.
5일부터 가능하다. 5일은 2일만에 상담을 끝내므로 15를 저장한다.
3일부터 생각을 해야 한다. 3일의 경우 3일에 상담을 실행하고, 남은 4일과 5일 중에 더 수익값을 높게 만들 수 있는 날짜를 선택해야 한다. 이 부분을 비교해주는 코드가 필요하다.
사실 이 예제에서는 4일에서 T값이 1이기 때문에 3,4,5 일을 연속해서 일을 할 수 있어서 이 부분이 필요가 없다. 하지만, 만약 4일의 T값이 2 이상이라면 비교해주는 부분이 반드시 필요하다.
해당 부분을 해결해야 하는 테스트케이스가 마지막 테케이다.
3일을 예로 들자면, 3일에서 "T3 직후의 수익값과 P3 의 합 = 4일의 P값"
과
"3일에서 T3 이후의 수익값 중 최대의 값의 합 = 4일 이후의 ans배열 중 최대값"
을 비교해주어야 한다.
개념적으로는 이해가 잘 안되고 코드를 보면 더 이해가 안된다. 하지만 논리적으로 뒤에서부터 차근차근 계산을 하다보면 아 이 부분을 고려해야 하는군! 하고 생각이 들것이다.
N = int(input())
arr = []
for i in range(N):
arr.append(list(map(int, input().split(" "))))
ans = [0 for i in range(N+1)]
def solution():
# 뒤에서 부터 dp 시작 N - Tn 이 0 초과면 불가능
# for 문 n부터 0으로
for i in range(N-1, -1, -1):
if i + arr[i][0] > N: # 상담이 불가능한 부분 확인(마지막상담)
ans[i] = 0
else:
ans[i] = max(arr[i][1] + max(ans[i+arr[i][0]:]), ans[i+arr[i][0]])
# 현재P값 T값 이후 부터 최대값 T값 직후 값
print(max(ans))
solution()