μκ° μ ν | λ©λͺ¨λ¦¬ μ ν |
---|---|
2μ΄ | 512MB |
μ€λλΆν° N+1μΌμ§Έ λλ λ ν΄μ¬νκΈ° μν΄μ λ¨μ NμΌ λμ μ΅λν λ§μ μλ΄νλ €κ³ ν¨.
κ°κ°μ μλ΄μ
<aside> π
μμ ) N = 7μΌ λ μλ΄ μΌμ ν
1μΌ | 2μΌ | 3μΌ | 4μΌ | 5μΌ | 6μΌ | 7μΌ | |
---|---|---|---|---|---|---|---|
$T_i$ | 3 | 5 | 1 | 1 | 2 | 4 | 2 |
$P_i$ | 10 | 20 | 10 | 20 | 15 | 40 | 200 |
1μΌμ μ‘νμλ μλ΄μ μ΄ 3μΌμ΄ κ±Έλ¦¬κ³ , λ°μ μ μλ κΈμ‘μ 10
5μΌμ μ‘νμλ μλ΄μ μ΄ 2μΌμ΄ κ±Έλ¦¬κ³ , λ°μ μ μλ κΈμ‘ 15
λν, 1μΌμ μλ΄μ νκ² λλ©΄ 2, 3μΌμλ μλ΄μ ν μ μμ.
2μΌμ μλ΄μ νκ² λλ©΄, 3, 4, 5, 6μΌμλ μλ΄μ ν μ μμ.
λν N + 1μΌμλ νμ¬μ μκΈ° λλ¬Έμ 6, 7μΌ μλ΄λ λΆκ°λ₯
β ν΄μ¬ μ μ ν μ μλ μλ΄μ μ΅λ μ΄μ΅μ 1, 4, 5μΌμ μλ΄μ μ§νν΄μ μ»λ 10 + 20 + 15 = 45
</aside>
β μλ΄μ μ μ ν νμ λ, λ°±μ€μ΄κ° μ»μ μ μλ μ΅λ μμ΅μ ꡬνλ νλ‘κ·Έλ¨
λ°±μ€μ΄κ° μ»μ μ μλ μ΅λ μ΄μ΅
<aside> π https://www.acmicpc.net/problem/15486
</aside>