[JavaScript/section 10] 04 - λμ κ΅ν
π λμ κ΅ν(λ μ μκ³ λ¦¬μ¦)
λ€μκ³Ό κ°μ΄ μ¬λ¬ λ¨μμ λμ λ€μ΄ μ£Όμ΄μ Έ μμλ κ±°μ€λ¦λμ κ°μ₯ μ μ μμ λμ μΌλ‘ κ΅νν΄μ£Όλ €λ©΄ μ΄λ»κ² μ£Όλ©΄ λλκ°? κ° λ¨μμ λμ μ 무νμ μΈ μ μλ€.
μ λ ₯μ€λͺ
첫 λ²μ§Έ μ€μλ λμ μ μ’ λ₯κ°μ N(1<=N<=12)μ΄ μ£Όμ΄μ§λ€. λ λ²μ§Έ μ€μλ Nκ°μ λμ μ μ’ λ₯κ° μ£Όμ΄μ§κ³ , κ·Έ λ€μμ€μ κ±°μ¬λ¬ μ€ κΈμ‘ M(1<=M<=500)μ΄ μ£Όμ΄μ§λ€.
κ° λμ μ μ’ λ₯λ 100μμ λμ§ μλλ€.
μΆλ ₯μ€λͺ
첫 λ²μ§Έ μ€μ κ±°μ¬λ¬ μ€ λμ μ μ΅μκ°μλ₯Ό μΆλ ₯νλ€.
μ λ ₯μμ | μΆλ ₯μμ |
3 1 2 5 15 |
3 (5 5 5) |
π νμ΄ λ°©λ²
DFSλ₯Ό μ¬μ©ν΄ μΆ©λΆν ν΄κ²°ν μ μλ λ¬Έμ μ΄μ§λ§ Nμ΄ 100 μ΄μ, Mμ΄ 10000 μ΄μμΌλ‘ 컀μ§λ€λ©΄ μκ°μ΄ μ€λ κ±Έλ¦°λ€λ λ¬Έμ κ° λ°μνλ€.
DP λ¬Έμ μμ μ λͺ ν λ μ μκ³ λ¦¬μ¦μ μ¬μ©ν΄ μ΄λ¬ν λ¬Έμ λ₯Ό ν΄κ²°ν μ μλ€.
- dy[j] - j κΈμ‘μ κ±°μ¬λ¬μ£Όλλ° μ¬μ©λ μ΅μ λμ μ κ°μ
- μμμ νμ΄ κ³Όμ μ€ ν μ₯λ©΄μ μμλ‘ λ³΄μ¬μ£Όμλ€. μ΄μ κ°μ κ³Όμ μ λ°λ³΅ν ν dy λ°°μ΄μ λ§μ§λ§ μμλ₯Ό answer λ³μμ ν λΉν΄μ£Όλ©΄ λλ€.
function solution(m, coin) {
let answer = 0;
// μ΅μ λμ μ κ°μλ₯Ό ꡬνλ λ¬Έμ μ΄λ―λ‘ μ΅λ λμ μ κ°μ 500(1 x 500)λ³΄λ€ ν° 1000μΌλ‘ μ΄κΈ°ν
let dy = Array.from({ length: m + 1 }, () => 1000);
// 0μμ κ±°μ¬λ¬μ£Όλλ° μ¬μ©λλ λμ μ κ°μλ μμΌλ―λ‘ 0μΌλ‘ μ΄κΈ°ν
dy[0] = 0;
for (let i = 0; i < coin.length; i++) {
for (let j = coin[i]; j <= m; j++) {
dy[j] = Math.min(dy[j], dy[j - coin[i]] + 1);
}
}
answer = dy[m];
return answer;
}
let arr = [1, 2, 5];
console.log(solution(15, arr));