문제설명

->링크<-

해결방법

dp[i]를 어떻게 설정할 지만 잡으면 어렵지만은 않은 문제이다.

dp[i]는 i날에 상담을 했을 때 받는 보수의 최댓값을 저장하고

저장하는 방식(점화식)은 이렇다

dp[i] = max(dp[i] + dp[1:i]중 1개 + P[i])일 것이다.

dp[1]부터 차근차근 쌓아가면 된다.

해답 코드

import sys
input = sys.stdin.readline
N = int(input().rstrip())

T = [-1]
P = [-1]

for _ in range(N):
  t, p = map(int, input().split())
  T.append(t)
  P.append(p)
#처음 위치 넣어주기
dp = [0] * (N+1)
if T[1] <= N:
  dp[1] = P[1]
for i in range(2, N+1):
  if T[i] + i - 1 <= N:
    dp[i] = P[i]
    #dp작성 가능
    for j in range(1, i):
      if T[j] + j -1 <= i-1:
        dp[i] = max(P[i] + dp[j], dp[i])
  else:
    #dp작성 불가
    dp[i] = 0

print(max(dp[1:]))
 

걸린시간

다른 사람의 코드를 보고난 후

대부분 나와 완전 다른 아이디어로 해결했다!!!
먼저 다른 풀이들은 dp를 이렇게 놨다

dp[i]는 i날부터 마지막 날까지 상담을 했을 때 보수의 최댓값이다!!!

따라서 i를 뒤에서부터 가면 반복하는 연산 없이
dp[i]는 dp[i] + dp[i+t[i]] 즉
i날 상담을 하고 그 바로 다음 가능한 날짜에서의 dp값을 더한게
dp[i]값이 될 것이다.

사실 이방법은 실전에서 못 떠올렸을 것 같다 왜냐하면 계속 앞에서만 쌓아가야 겠다고 생각했기 때문이다!!! 하지만 다음부터 dp문제를 볼때는 뒤에서부터 쌓는 방법도 한번은 생각해 볼 수 있을 것 같다.