[14501] ํ‡ด์‚ฌ

jiholeeยท2022๋…„ 6์›” 2์ผ
0

์•Œ๊ณ ๋ฆฌ์ฆ˜

๋ชฉ๋ก ๋ณด๊ธฐ
18/20

ํ‡ด์‚ฌ

๐Ÿ“Œ ๋’ค์ชฝ ๋‚ ์งœ๋ถ€ํ„ฐ ๊ฑฐ๊พธ๋กœ ํ™•์ธํ•˜๋Š” ๋ฐฉ์‹์œผ๋กœ ์ ‘๊ทผํ•˜๊ธฐ

n = int(input())
t = [] # ์ƒ๋‹ด ๊ธฐ๊ฐ„
p = [] # ์ƒ๋‹ด ๊ธˆ์•ก
d = [0] * (n+1)
mx = 0

for _ in range(n):
    x, y = map(int, input().split())
    t.append(x)
    p.append(y)
    
for i in range(n-1, -1, -1): 
    # i - ํ˜„์žฌ ์ƒ๋‹ด / time - ํ˜„์žฌ ์ƒ๋‹ด ๋๋‚˜๊ณ 
    time = t[i] + i
    
    # ์ƒ๋‹ด์ด ๊ธฐ๊ฐ„ ์•ˆ์— ๋๋‚˜๋Š” ๊ฒฝ์šฐ
    if time <= n:
        d[i] = max(p[i] + d[time], mx)
        mx = d[i]
    else:
        d[i] = mx
# print(d)
print(mx)

dp์ข€ ์ž˜ํ•˜๊ณ  ์‹ถ๋‹ค๐Ÿ˜ต

0๊ฐœ์˜ ๋Œ“๊ธ€