[백준/15486/파이썬] 퇴사2

https://www.acmicpc.net/problem/15486

15486번: 퇴사 2

Problem

• 퇴사 문제랑 똑같다. 입력의 크기만 조절 했음.
•  

조건

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

SOL

이전에는 DFS+Backtracking으로 풀었다.

하지만, 그건 입력이 작았고, 완탐으로 충분히 가능하다는 판단이 서서 풀었던거임.

이번에는 1,500,000 으로, O(N)으로 풀어야할거 같음.즉, DP로 재귀를 줄여야한다.

DP로 접근을 한다고 생각하면, 항상 시작점, 끝나는점, 끝나는 조건 등을 생각해줘야함.

하지만, 이 문제에서 시작점을 첫번째 날이라고 생각하게되면, 첫번째날 시작하는게 최대일 수도,

두번째날 시작하는게 최대일 수 도 있기 때문에, 이중반복을 해야한다.

변수를 하나 선언해서, 반복을 줄여보자. 내가 필요한 정보는 어차피, 제일 큰 값을 항상 가지고 있으면 되는거임.

(누적된 값이 필요하기 때문) 

 

1. 정의: DP[N]는 N번째 날 까지의 최댓값.
2. 구하는 값: max(DP)
3. 초기값 : DP[N] = 0
4. 점화식: DP[i] = max( DP[i+1], DP[i+T[i]]+P[i] ) , T[i] = 걸리는 시간, P[i] = 가격 

import sys
input = sys.stdin.readline

N = int(input().rstrip())
T= []
P= []
DP=[0]*(N+1)
for _ in range(N):
	time,price=map(int,input().split())
	T.append(time)
	P.append(price)

max_value=0
for i in range(N):
    max_value=max(max_value,DP[i])
    if i+T[i] >N:
        continue
    DP[i+T[i]] = max(DP[i+T[i]],max_value+P[i])


#print(DP)
print(max(DP))