1. 문제 설명

퇴사 2

2. 문제 분석

i번 날 진행한 상담 종료일이 퇴사날보다 전이라면 이 상담을 한 경우와 하지 않은 경우 중 최댓값을 마지막 상담 종료일로 업데이트한다. 상담을 한 경우의 이득은 지금까지 dp에 기록한 값 중 가장 큰 값에 i번 상담을 한 이득을 더한 값이다.

• 인덱스를 거꾸로 돌려가면서도 문제를 풀 수 있었다.

상담 종료일 n번부터 거꾸로 확인하면서 상담이 가능하고, 상담 종료일이 해당 종료일에 기록된 dp보다 크다면 얻은 이득만큼 누적된 부분에 추가, 상담 시작일부터 종료일까지는 상담 비용으로 갱신해준다. 하지만 이때 이중 for 문으로 체크해야 하고, 업데이트 파트가 비효율적이기 때문에 시간 초과가 나왔다.

3. 나의 풀이

import sys

n = int(sys.stdin.readline().rstrip())
t = []
p = []
for _ in range(n):
    small_t, small_p = map(int, sys.stdin.readline().rstrip().split())
    t.append(small_t)
    p.append(small_p)

dp = [0 for _ in range(n+1)]
local_max = dp[0]

for i in range(n):
    local_max = max(local_max, dp[i])
    # i번까지 얻을 수 있는 dp 중 최댓값 local_max

    last_idx = t[i] + i
    # i번 상담을 할 경우 last_idx날까지 상담해야 한다.
    if last_idx > n: continue
    # 상담 자체를 하지 못하는 경우
    dp[last_idx] = max(local_max + p[i], dp[last_idx])
    # last_idx 날까지 i번 상담을 한다면 p[i]를 더한 값으로 갱신
    # 상담을 하지 않는 이득이 더 크다면 그대로.

print(max(dp))
# 모든 상담 가능한 dp에서 얻을 수 있는 가장 큰 이득