2294 동전2 (자바스크립트)

문제

n가지 종류의 동전이 있다. 이 동전들을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그러면서 동전의 개수가 최소가 되도록 하려고 한다. 각각의 동전은 몇 개라도 사용할 수 있다.

입력

첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주어질 수도 있다.

출력

첫째 줄에 사용한 동전의 최소 개수를 출력한다. 불가능한 경우에는 -1을 출력한다.

=====

문제 분석

동전이 1원 5원 12원이 있을 때, 15원을 만드는 방법은 

1. 1원 15개 

2. 5원 3개

3. 5원 2개 1원 5개 

3. 12원 1개, 1원 3개

등등의 방법이 있다. 

이 중 타겟을 만드는데 가장 적은 동전의 갯수를 출력해주면 된다.

오답 노트

처음에는 갖고 있는 동전을 내림차순으로 정렬한 뒤 이중 반복문을 돌려서 최대한 나눠주는 것으로 해결할려 했다.

그리고 나오는 동전의 갯수를 dp에 등록해놓으면서 최종적으로 dp[target]을 출력할려 했는데 틀림.

이럴 경우 완전 탐색이 불가능해져서 모든 경우의 수를 찾을 수 없다.

따라서 1원부터 target까지의 모든 경우의 수를 탐색하면서 

dp[current] = MIN(dp[current-갖고 있는 코인]+1, dp[current]) 라는 점화식으로 해결 

1. 우선 갖고 있는 코인을 오름차순 정렬한 뒤 만들 수 있는 금액들을 dp에 넣어줌

2. 오름차순 한 뒤 dp에 넣는 것이므로 나눗셈 몫이 제일 작은 값이 항상 dp에 들어가는게 보장 됨.

3. 이후 1원부터 시작하여 각 금액을 탐색하면서, 갖고 있는 동전으로 만들 수 있는 경우의 수를 찾는 것으로 완전 탐색 진행

const INF = 1_000_000_001;

const main = (input) => {
    const [n, target] = input
        .shift()
        .split(' ')
        .map((v) => +v);
    const coin = [];
    const dp = Array.from({ length: target + 1 }).fill(INF);
    input.forEach((c) => {
        coin.push(+c);
    });
    coin.sort((a, b) => a - b);
    for (let i = 0; i < coin.length; i++) {
        let c = coin[i];
        for (let j = 1; j * c <= target; j++) {
            dp[c * j] = j;
        }
    }
    for (let i = 1; i <= target; i++) {
        for (let j = 0; j < coin.length; j++) {
            const c = coin[j];

            if (i - c < 0) continue;
            if (dp[i - c] === -1) continue;
            dp[i] = Math.min(dp[i - c] + 1, dp[i]);
        }
    }

    if (dp[target] === INF) {
        console.log(-1);
    } else {
        console.log(dp[target]);
    }
};
const input = require('fs')
    .readFileSync(process.platform === 'linux' ? '/dev/stdin' : './input.txt')
    .toString()
    .trim()
    .split('\n');

main(input);