[BOJ] 11047 동전() with JavaScript

JavaScript를 이용한 백준 11047 동전() 문제를 풀이한 글입니다.

문제

준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다.

동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000)

둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수)

출력

첫째 줄에 K원을 만드는데 필요한 동전 개수의 최솟값을 출력한다.

풀이

처음 문제를 읽고 방법을 떠올리때 가장 처음 드는 직관적인 방법은
큰 동전부터 차례대로 최대치를 넣어서 진행하는 방법이다.
어떠한 코인을 사용할 수 있는가 금액이 얼마냐에 따라 해당 방법의 사용 가능 여부가 결정된다.
다만, 해당 문제의 경우 (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) 조건으로 인해 모든 코인은 자신보다 작은 코인의 곱의 형태로 나타 낼수 있고 A1 = 1이므로 주어진 모든 K값은 반드시 만들 수 있게 된다.
즉 A1 K개를 가장 큰 코인부터 차례대로 최대치를 만들어서 내려가는 방식으로 생각 할 수 있고 이는 분명히 가장 작은 개수를 만족하게 된다.

알고리즘

• 나머지 값을 동전의 값으로 나눈다.
• 몫을 카운트에 더한다
• 나머지를 갱신한다.

나머지가 0이 될 때까지 반복한다.

구현

/**
 * https://www.acmicpc.net/problem/11047
 * 
 * hint: (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수)
 * 위 조건으로 인해 모든 코인은 하위 코인의 배수로 만들수 있게 된다.
 * 즉 Ai 코인은 Aj (1 ≤ j ≤ i-1) 코인의 곱으로 나타 낼수 있다.
 * 코인으로 만들고자 하는 값이 애초에 불가한 값이 아닌경우
 * 상위코인부터 차례대로 채워 나가면 코인의 개수가 가장 작아지게 된다.
 */
const fs = require('fs');
const input = fs.readFileSync('./input.txt').toString().trim().split('\n');
const [N, K] = input.shift().split(' ').map(Number);
const coins = input.map(Number).filter(value => value <= K).reverse();

let count = 0;
let remain = K;

for (let coin of coins) {
    if (remain === 0)
        break;

    count +=  Math.floor(remain / coin);
    remain %= coin;
}

console.log(count);