leah

my dev_log

0%

BOJ 14501

Posted on In ,

Input

첫째 줄에 N (1 ≤ N ≤ 15)이 주어진다.

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

1
2
3
4
5
6
7
8
9
10
11
N = int(input())
T = []
P = []
dp = []

for _ in range(N):
  t, p = map(int, input().split())
  T.append(t)
  P.append(p)
  dp.append(p)
dp.append(0)

Output

첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다.

1
print(dp[0])

DP

역순으로 접근해 무조건 index 0 값에 최대를 담도록 함.

  • 현재 일자 i 에 기간 T[i] 를 더했을 때 N+1 보다 작아야 하므로, 예외의 경우 이전 값 dp[p+1] 을 유지한다.

    1
    2
    if i+T[i] > N:
      dp[i] = dp[i+1]

  • 범위 내에 드는 경우 최대 이익을 구하는 조합 을 구해야 하므로, 이전 값 dp[i+1] 과 현재 비용 P[i] 에 T[i] 이후의 비용을 더한 값 중 max 값을 취한다.

    1
    2
    else:
      dp[i] = max(dp[i+1], P[i]+dp[i+T[i]])