λ¬Έμ
μλ΄μμΌλ‘ μΌνκ³ μλ λ°±μ€μ΄λ ν΄μ¬λ₯Ό νλ €κ³ νλ€.
μ€λλΆν° N+1μΌμ§Έ λλ λ ν΄μ¬λ₯Ό νκΈ° μν΄μ, λ¨μ NμΌ λμ μ΅λν λ§μ μλ΄μ νλ €κ³ νλ€.
λ°±μ€μ΄λ λΉμμκ² μ΅λν λ§μ μλ΄μ μ‘μΌλΌκ³ λΆνμ νκ³ , λΉμλ ν루μ νλμ© μλ‘ λ€λ₯Έ μ¬λμ μλ΄μ μ‘μλμλ€.
κ°κ°μ μλ΄μ μλ΄μ μλ£νλλ° κ±Έλ¦¬λ κΈ°κ° Tiμ μλ΄μ νμ λ λ°μ μ μλ κΈμ‘ Piλ‘ μ΄λ£¨μ΄μ Έ μλ€.
N = 7μΈ κ²½μ°μ λ€μκ³Ό κ°μ μλ΄ μΌμ νλ₯Ό 보μ.
1μΌ2μΌ3μΌ4μΌ5μΌ6μΌ7μΌTiPi3 | 5 | 1 | 1 | 2 | 4 | 2 |
10 | 20 | 10 | 20 | 15 | 40 | 200 |
1μΌμ μ‘νμλ μλ΄μ μ΄ 3μΌμ΄ 걸리며, μλ΄νμ λ λ°μ μ μλ κΈμ‘μ 10μ΄λ€. 5μΌμ μ‘νμλ μλ΄μ μ΄ 2μΌμ΄ 걸리며, λ°μ μ μλ κΈμ‘μ 15μ΄λ€.
μλ΄μ νλλ° νμν κΈ°κ°μ 1μΌλ³΄λ€ ν΄ μ μκΈ° λλ¬Έμ, λͺ¨λ μλ΄μ ν μλ μλ€. μλ₯Ό λ€μ΄μ 1μΌμ μλ΄μ νκ² λλ©΄, 2μΌ, 3μΌμ μλ μλ΄μ ν μ μκ² λλ€. 2μΌμ μλ μλ΄μ νκ² λλ©΄, 3, 4, 5, 6μΌμ μ‘νμλ μλ΄μ ν μ μλ€.
λν, N+1μΌμ§Έμλ νμ¬μ μκΈ° λλ¬Έμ, 6, 7μΌμ μλ μλ΄μ ν μ μλ€.
ν΄μ¬ μ μ ν μ μλ μλ΄μ μ΅λ μ΄μ΅μ 1μΌ, 4μΌ, 5μΌμ μλ μλ΄μ νλ κ²μ΄λ©°, μ΄λμ μ΄μ΅μ 10+20+15=45μ΄λ€.
μλ΄μ μ μ ν νμ λ, λ°±μ€μ΄κ° μ»μ μ μλ μ΅λ μμ΅μ ꡬνλ νλ‘κ·Έλ¨μ μμ±νμμ€.
μ λ ₯
첫째 μ€μ N (1 β€ N β€ 1,500,000)μ΄ μ£Όμ΄μ§λ€.
λμ§Έ μ€λΆν° Nκ°μ μ€μ Tiμ Piκ° κ³΅λ°±μΌλ‘ ꡬλΆλμ΄μ μ£Όμ΄μ§λ©°, 1μΌλΆν° NμΌκΉμ§ μμλλ‘ μ£Όμ΄μ§λ€. (1 β€ Ti β€ 50, 1 β€ Pi β€ 1,000)
μΆλ ₯
첫째 μ€μ λ°±μ€μ΄κ° μ»μ μ μλ μ΅λ μ΄μ΅μ μΆλ ₯νλ€.
μμ μ λ ₯ 1 볡μ¬
7
3 10
5 20
1 10
1 20
2 15
4 40
2 200
μμ μΆλ ₯ 1 볡μ¬
45
μμ μ λ ₯ 2 볡μ¬
10
1 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
μμ μΆλ ₯ 2 볡μ¬
55
μμ μ λ ₯ 3 볡μ¬
10
5 10
5 9
5 8
5 7
5 6
5 10
5 9
5 8
5 7
5 6
μμ μΆλ ₯ 3 볡μ¬
20
μμ μ λ ₯ 4 볡μ¬
10
5 50
4 40
3 30
2 20
1 10
1 10
2 20
3 30
4 40
5 50
μμ μΆλ ₯ 4 볡μ¬
90
# νμ΄ λ°©λ²
dpλ NμΌμ μ»μ μ μλ μ΅λ μ΄μ΅μ μλ―Ένλ€.
κ·Έλ¦¬κ³ NμΌμ μ»μ μ μλ μ΄μ΅μ N-1μΌκΉμ§μ κ²°κ³Όλ₯Ό ν΅ν΄ μ»μ΄μ§κΈ° λλ¬Έμ
forλ¬Έμ λ λ λ―Έλλ₯Ό κ³ λ €ν΄μΌνλ€. λ°λΌμ λ°°μ΄μ ν¬κΈ°λ N+1μ΄ μλ N+2λ‘ μ€μ νλ€.
μμ§ν μ²μμ ν λλ λ§λ§νλ€.. dpμ μ΅μν΄μ ΈμΌ ν λ― γ
# μ½λ
# 2025-04-20 10:40-11:25 (νμ΄μ°Έκ³ )
import sys
# sys.stdin = open("input.txt","r")
N = int(sys.stdin.readline())
table = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
dp = [0] * (N + 2) # dp[i] = iμΌμ μ»μ μ μλ μ΅λ μμ΅
for i in range(1, N + 1):
t, p = table[i - 1]
# μ€λ(iμΌ)μ μ무κ²λ νμ§ μκ³ κ·Έλ₯ λμ΄κ°λ κ²½μ°λ κ³ λ €
dp[i + 1] = max(dp[i + 1], dp[i])
# μ€λ(iμΌ)μ μλ΄μ νλ€λ©΄
if i + t - 1 <= N:
dp[i + t] = max(dp[i + t], dp[i] + p)
print(max(dp)) # N+1μΌμ λλ¬μ μλ μμ΄μ μ 체 μ€ max
'π Study > Baekjoon' μΉ΄ν κ³ λ¦¬μ λ€λ₯Έ κΈ
[Gold IV] 1107 - 리λͺ¨μ»¨ (0) | 2025.04.25 |
---|---|
[Gold IV] 14502 - μ°κ΅¬μ (0) | 2025.04.25 |
[Silver I] 1699 - μ κ³±μμ ν© (0) | 2025.04.19 |
[Silver I] 1389 - μΌλΉ λ² μ΄μ»¨μ 6λ¨κ³ λ²μΉ (0) | 2025.04.19 |
[Silver III] 2606 - λ°μ΄λ¬μ€ (0) | 2025.04.19 |