https://www.acmicpc.net/problem/14501
시간 2초, 메모리 512MB
input :
- N (1 ≤ N ≤ 15)
- Ti Pi(1 ≤ Ti ≤ 5, 1 ≤ Pi ≤ 1,000)
output :
- 백준이가 얻을 수 있는 최대 이익을 출력
역시 봤었던 문제가 제일 문제인 것 같다 ㅋㅋㅋㅋㅋㅋㅋㅋ
앞에서 부터 할 경우 사용하는 변수가 매우 많아질 것 같고 중간에 겹치는 부분을 계산해 줘야 한다.
뒤에서 부터 계산을 하는 것이 편하다.
두가지 조건이 생기는 데.
1. 현재 상담을 수행할 경우 퇴사 날짜를 지나 버릴 때 .
2. 현재 상담을 수행할 수 있다. (여기에서 다시 2가지. - 현재 상담을 수행하는 것이 이득인지, 아니면 하지 않는 것이 나은지)
이 2. 의 경우를 보기 위해서 1번 예시를 보는 것이 가장 이해 하기 쉽다.
7
3 10
5 20
1 10
1 20
2 15
4 40
2 200
위의 예시에서 index 2번 5 20 을 보면
그 이전까지의 최대값은 45 이다. index 3, 4, 5를 다 수행한 경우
그리고 index 2번을 수행 할지 말지를 생각해야 하는데
수행 한다면 20 + data[index(2) + 5] 번째의 값을 얻게 된다.
수행 하지 않은 경우엔 지금까지의 최댓값 45를 받아온다.
그래서 이 둘의 max값을 비교해주는 것이다.
언제나 이런 포인터가 애매해지는 경우에는 뒤에서 부터 시작하는 경우가 많은 것 같다.
import sys
n = int(sys.stdin.readline())
data = [[0] * n for i in range(2)]
for i in range(n):
t, p = map(int, sys.stdin.readline().split())
data[0][i] = t
data[1][i] = p
dp = [0] * (n + 1)
for i in range(n - 1, -1, -1):
if i + data[0][i] > n:
dp[i] = dp[i + 1]
else:
dp[i] = max(dp[i + 1], data[1][i] + dp[i + data[0][i]])
print(dp[0])
