BOJ 15486

Input

첫째 줄에 N (1 ≤ N ≤ 1,500,000)이 주어진다.

둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 50, 1 ≤ Pi ≤ 1,000)

import sys
input = sys.stdin.readline

n = int(input())
T = []
P = []
dp = [0]*(n+1)
for _ in range(n):
  t, p = map(int, input().split())
  T.append(t)
  P.append(p)

퇴사1 문제의 코드는 시간 초과가 떴는데, 차이는 빌트인 input 대신 sys.stdin.readline 을 썼다는 점이다.

DP

처음부터 시작하는 방식으로 문제를 풀어봤으나, 당연히 스킵해도 될 만한 케이스까지 체크하고 있었다. 이전에 퇴사1 문제에서 뒤에서부터 접근하며 문제를 풀었던 기억이 있어, 뒤에서부터 시작하는 방식으로 문제를 풀어나가니 필요없는 과정은 스킵하고 비교해야 할 대상만 비교하고 있었다. 그래서 뒤에서부터 접근하는 방식을 토대로 문제를 풀어봄.

# 최대값을 구하기 위해 기존 dp 값과 대상값 비교
for i in range(n-1, -1, -1):

일단 기본적으로, 연속적으로 답을 구해나가는 게 아니라 기존의 값보다 큰 값이 존재할 경우 대체해야 하는 최대값 구하기 문제이기 때문에,

• max를 사용하여 기존의 dp 값 과 이전 값 + 현재 값 을 비교해서 큰 값을 dp 에 저장

해야 한다는 것만 대강 잡고 문제를 풀어나갔다.

주어진 조건이

• 퇴사 이후에는 일을 할 수 없음

이기 때문에, i + T[i] > n 일 경우에는 P를 계산하는 과정이 스킵된다. 난 조건을 만족하는 경우에만 체크하는 if문을 작성하고 dp를 애초에 0으로 초기화해서, else로 예외처리를 안 해도 된다고 착각했는데 if를 사용할 때는 꼭 else 조건도 생각해보자! 해당 범위를 벗어나는 경우에는 P는 계산하지 않지만 이전의 dp 값을 받아와야 한다. 즉, 0으로 무조건 초기화하면 안 되고 dp를 가져와야 한다는 것… 주어진 예시에서는 퇴사 직전에만 일자를 벗어나지만 중간에 범위를 벗어나는 경우에는 0으로 초기화하면 dp 값을 제대로 전달하지 못한다. 반례로

"""
7
3 10
5 20
1 10
5 20
2 15
4 40
2 200
"""

위의 경우에서 T[3]은 5이기 때문에 퇴사 일자를 넘어서는데, dp[3]에 0을 저장하면 정상적으로 코드가 작동하지 않을 것임.

else:
  dp[i] = dp[i+1]

• 퇴사 전에 일이 해결될 경우,

  • 마지막 날이라면 P를 그대로 받아오고 (dp를 0으로 초기화해서 생성했기 때문에)

  • 그 외에는

    1. 해당 일자의 일을 스킵할 경우
    2. 해당 일자의 일을 받아들일 경우

    위 2가지 경우 중 max 값을 취하면 된다.

# 퇴사 전까지만
if i + T[i] <= n:
  if i == n-1:
    dp[i] = P[i]
  else:
    dp[i] = max(dp[i+1], dp[i + T[i]] + P[i])

Output

print(dp[0])