๋ฌธ์
https://www.acmicpc.net/problem/15486
๋ฐฑ์ค ๋ฌธ์ ์ง - 0x10๊ฐ - ๋ค์ด๋๋ฏน ํ๋ก๊ทธ๋๋ฐ
์๊ณ ๋ฆฌ์ฆ: ๋ค์ด๋๋ฏน ํ๋ก๊ทธ๋๋ฐ
ํ์ด
์๋ด์์ผ๋ก ์ผํ๊ณ ์๋ ๋ฐฑ์ค์ด๋ ํด์ฌ๋ฅผ ํ๋ ค๊ณ ํ๋ค.
์ค๋๋ถํฐ N+1์ผ์งธ ๋๋ ๋ ํด์ฌ๋ฅผ ํ๊ธฐ ์ํด์, ๋จ์ N์ผ ๋์ ์ต๋ํ ๋ง์ ์๋ด์ ํ๋ ค๊ณ ํ๋ค.
๋ฐฑ์ค์ด๋ ๋น์์๊ฒ ์ต๋ํ ๋ง์ ์๋ด์ ์ก์ผ๋ผ๊ณ ๋ถํ์ ํ๊ณ , ๋น์๋ ํ๋ฃจ์ ํ๋์ฉ ์๋ก ๋ค๋ฅธ ์ฌ๋์ ์๋ด์ ์ก์๋์๋ค.
๊ฐ๊ฐ์ ์๋ด์ ์๋ด์ ์๋ฃํ๋๋ฐ ๊ฑธ๋ฆฌ๋ ๊ธฐ๊ฐ Ti์ ์๋ด์ ํ์ ๋ ๋ฐ์ ์ ์๋ ๊ธ์ก Pi๋ก ์ด๋ฃจ์ด์ ธ ์๋ค.
์๋ด์ ์ ์ ํ ํ์ ๋, ๋ฐฑ์ค์ด๊ฐ ์ป์ ์ ์๋ ์ต๋ ์์ต์ ๊ตฌํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค.
๋ฌธ์ ์์ฒด๋ 14501: ํด์ฌ์ ๋์ผํ๋ค.
๊ทธ๋์ ํน์๋ ํ๊ณ ์ด์ ํ์ด๋ฅผ ๊ทธ๋๋ก ์ ์ถํด๋ดค๋๋ ์๊ฐ์ด๊ณผ๋ค.
์ ๋ฒ์ฒ๋ผ ์ด์ค for๋ฌธ์ผ๋ก ํ๋ํ๋ ๋น๊ตํด๊ฐ๋ฉฐ ์ ๋ฐ์ดํธํ๋ฉด ๋ฐ๋ก ์๊ฐ์ด๊ณผ๋ฅผ ๋ฐ๋๋ค.
์ค๋ณต ์ฒดํฌ๋ฅผ ํผํ๋ ค๋ฉด ์ญ์์ผ๋ก ๊ณ์ฐํด์ผํ๋ค.
์ฆ, dp[i] = i๋ฒ์งธ ๋ ๋ถํฐ ํด์ฌ์ผ๊น์ง ์ป์ ์ ์๋ ์ต๋ ๊ธ์ก์ ๋ํ๋ด๊ฒ ๋๋ค.
๋ฐ๋ผ์ i๋ฒ์งธ๋ ์ ์๋ด์ ํ์ง ์๋๋ค๋ฉด, i+1๋ฒ์งธ ๋ ์ ์ต๋๊ฐ์ ๊ฐ์ ธ์์ผํ๋ค.
์ญ์์ด๊ธฐ ๋๋ฌธ์ ๋ฏธ๋์ ๊ฐ์ผ๋ก ํ์ฌ์ ๊ฐ์ ์ฑ์ฐ๋ ๊ตฌ์กฐ๊ฐ ๋๋ค.
๊ทธ๋ฌ๋ฏ๋ก dp๋ฅผ N+1๋งํผ ์์ฑ ํ N-1๋ถํฐ 0๋ฒ์งธ ๊น์ง ์ํํ๋ค.
(N๋งํผ๋ง ์์ฑํ๋ ๋ฐฉ๋ฒ๋ ์์ง๋ง ์ง๊ด์ ์ด์ง ์์.)
์กฐ๊ฑด์ ํ๋๋ง ์ฒดํฌํ๋ฉด ๋๋ค.
ํ์ฌ ์๋ด์ผ์ i + ์์๊ธฐ๊ฐ Ti ๊ฐ N์ ์ด๊ณผํ๋์ง ํ์ธํ๊ณ , ์ด๊ณผํ๋ค๋ฉด i+1๋ ์ ์ต๋๊ฐ์ ๊ฐ์ ธ์จ๋ค.
์ด๊ณผํ์ง ์๋๋ค๋ฉด i๋ฒ ์๋ด์ ์ก์ ์ ์๋ค๋ ๋ป์ด๋ฏ๋ก (ํ์ฌ ์๋ด์ ์ํํ์ง ์๋ ๊ฒฝ์ฐ dp[i+1], ์ํํ๋ ๊ฒฝ์ฐ Pi + dp[i๋ฒ ์๋ด์ด ๋๋ ํ])๋ฅผ ๋น๊ตํ์ฌ ๋ ํฐ๊ฐ์ผ๋ก ์ ๋ฐ์ดํธํ๋ค.
๋ชจ๋ ์ํ๋ฅผ ๋๋ด๋ฉด ์ฒซ๋ฒ์งธ๋ ๋ถํฐ ์์ํ ๊ฒฝ์ฐ์ ์ต๋๊ฐ dp[0]์ ์ถ๋ ฅํ๋ค.
์ ์ฒด ์ฝ๋
# โญ ์๊ฐ ๋จ์ถ ์์ธ: ํํ ์ฌ์ฉ, (time, pay)์ ๊ฐ์ด ์ธํจํน
# ๋ฉ๋ชจ๋ฆฌ: 252484KB / ์๊ฐ: 2044ms
from sys import stdin
input = stdin.readline
N = int(input())
lst = [tuple(map(int, input().split())) for _ in range(N)]
dp = [0] * (N + 1)
for i in range(N - 1, -1, -1): # ์ญ์์ผ๋ก ์ํ
time, pay = lst[i]
if i + time > N: # ์๋ด ์ข
๋ฃ์ผ์ด ํด์ฌ์ผ ์ดํ
dp[i] = dp[i + 1]
else:
# ํ์ฌ ์๋ด์ ์ํํ๋ ๊ฒฝ์ฐ์ ์ํํ์ง ์๋ ๊ฒฝ์ฐ ์ค ์ต๋๊ฐ
dp[i] = max(dp[i + 1], pay + dp[i + time])
print(dp[0])
์ฐธ๊ณ ๋ก tuple()๋์ list()๋ฅผ ์ฌ์ฉํ๊ณ time, pay ๋์ lst[i][0], lst[i][1]๋ก ์ฌ์ฉํ์๋ → ๋ฉ๋ชจ๋ฆฌ: 346424KB / ์๊ฐ: 2832ms ์๋ค...
์๊ฐ๋ณด๋ค ์ฐจ์ด๊ฐ ์ปค์ ๋๋๋ค;;
๋๋ถ์ dp๋ฅผ N๋งํผ ์์ฑํ์๋๋ณด๋ค ๋ ํจ์จ์ ์ธ ๊ฒฐ๊ณผ๊ฐ ๋์๋ค.
ํํ, ์ธํจํน ์ฉ์ !