[백준 15486번] 퇴사 2 문제풀이

< 문제 >

 

 

 

< 입출력 >

<풀이>

날짜당 걸리는 시간과 받을 수 있는 가격을 저장한 후, 다이나믹 프로그래밍을 통해 1번째날부터 받을 수 있는 가장 큰 값을 저장한다.  

 

 

< 시도 1 >

import sys
n = int(sys.stdin.readline())
time = [0 for i in range(n)]
price = [0 for i in range(n)]
max_price = [0 for i in range(n+1)]

for i in range(n):                  # 시간과 가격 입력 받기
    time[i], price[i] = map(int, sys.stdin.readline().split())

for i in range(n):
    if i + time[i] < n + 1:
        max_price[i + time[i]] = max(max_price[i] + price[i], max_price[i+time[i]])
        max_price[i + 1] = max(max_price[i+1], max_price[i])

print(max(max_price))

 

 

< 시도2 >

import sys
n = int(sys.stdin.readline())

t, p = [0 for _ in range(n + 1)], [0 for _ in range(n + 1)]
for i in range(1, n + 1):
    t[i], p[i] = map(int, input().split())

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

for i in range(1, n + 1):
    dp[i] = max(dp[i], dp[i - 1])      # 이전까지의 최댓값
    fin_date = i + t[i] - 1            # 당일 포함
    if fin_date <= n:                  # 최종일 안에 일이 끝나는 경우
        dp[fin_date] = max(dp[fin_date], dp[i - 1] + p[i])     # i일부터는 일을 해야하므로 i일에 얻을 수 있는 최댓값이 아닌 i-1일까지 얻을 수 있는 최댓값을 구한다
print(max(dp))

성공!!