취준/백준
[백준][Python][14501][15486][DP]퇴사, 퇴사2
puff
2020. 2. 27. 09:38
문제 : https://www.acmicpc.net/problem/14501
14501번: 퇴사
첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다.
www.acmicpc.net
문제:https://www.acmicpc.net/problem/15486
15486번: 퇴사 2
첫째 줄에 N (1 ≤ N ≤ 1,500,000)이 주어진다. 둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 50, 1 ≤ Pi ≤ 1,000)
www.acmicpc.net
DP 문제다.
둘 다 푸는 방법은 같고 개수만 15, 1500000개로 다르다. 따라서, 퇴사 1 은 O(N^2)로 풀어도 되지만 퇴사 2는 O(N)으로 풀어야 한다.
i 번째 날, 일을 선택했을 때는
i 번째에 일을 선택해서 t[i]까지 한 값 = max(i번째까지 와서 벌은 돈의 최댓값 + 현재 i번째 일을 할 경우, 일을 안 하고 넘어갈 경우)
로 풀 수 있다.
import sys
n = int(input())
t,p = [],[]
dp = [0]*(n+1)
for i in range(n):
tmp = [int(i) for i in sys.stdin.readline().split()]
t.append(tmp[0])
p.append(tmp[1])
cmax = 0
for i in range(n):
cmax = max(cmax,dp[i])
if i+t[i] > n:
continue
dp[i+t[i]] = max(cmax+p[i], dp[i+t[i]])
print(max(dp))