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
참고한 글
https://velog.io/@sunkyuj/python-%EB%B0%B1%EC%A4%80-15486-%ED%87%B4%EC%82%AC-2
[python] 백준 15486 : 퇴사 2
문제 링크https://www.acmicpc.net/problem/15486대충 봐도 dp 문제라는 것을 알 수 있다.우선 N이 150만까지이므로 O(N)이나 O(NlogN)의 복잡도를 가진 알고리즘을 생각해볼 수 있다.어차피 최댓값만 구하면 되
velog.io
아직 이해를 다 못 했다 ......
import sys
input = sys.stdin.readline
# 그날 상담을 시작하는 경우 / 그날 상담을 시작하지 않는 경우
# 상담 시작한다면, 상담 끝난 다음날 수익이 증가
# M은 이전에 저장된 M의 값과 dp[i]중 큰 것으로 갱신
# dp[i]는 '현재까지 수익에 이번 상담의 수익을 더한 값' or '오늘의 상담이 끝나는 시점의 수익'
n = int(input())
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: # 최종일 안에 일이 끝나는 경우
# i일부터는 일을 해야하므로 i일에 얻을 수 있는 최댓값이 아닌 i-1일까지 얻을 수 있는 최댓값을 구한다
# print(i, dp, dp[fin_date], dp[i-1], p[i])
dp[fin_date] = max(dp[fin_date], dp[i - 1] + p[i])
print(max(dp))