[백준 / node.js] 11047번: 동전 0

출처: 백준

11047번: 동전 0

문제

준규가 가지고 있는 동전은 총 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

10 4200

1

5

10

50

100

500

1000

5000

10000

50000

예제 출력 1

6

예제 입력 2

10 4790

1

5

10

50

100

500

1000

5000

10000

50000

예제 출력 2

12

내 코드

const readline = require("readline");
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

let input = [];

rl.on("line", function (line) {
  input.push(line.split(" ").map((el) => +el));
}).on("close", function () {
  const N = input[0][0];
  let K = input[0][1];
  let count = 0;
  let coins = [];

  // 동전 종류
  for (let i = 1; i <= N; i++) {
    coins.push(input[i]);
  }

  // 가장 큰 동전먼저 계산
  for (let j = coins.length; j >= 0; j--) {
    if (coins[j] <= K) {
      count += Math.floor(K / coins[j]);
      K = K % coins[j];
    }
  }

  console.log(count);
  process.exit();
});

결과

> 10 4200 > 1 > 5 > 10 > 50 > 100 > 500 > 1000 > 5000 > 10000 > 50000 6

> 10 4790 > 1 > 5 > 10 > 50 > 100 > 500 > 1000 > 5000 > 10000 > 50000 12

 

동전을 최소한으로 사용해서 주어진 가치를 만들기 위해 몇 개의 동전이 필요한 지 구하는 문제이다.

주어진 10가지의 동전의 종류를 배열에 담고 나눌 수 있는 가장 큰 동전부터 나누어주면 된다.

4200원이면 1000원짜리 동전 4개, 그리고 나머지 200에서 나눌 수 있는 가장 큰 동전으로 또 나누어 준다.

100원짜리 동전 2개가 더 필요하다.

count변수에는 몫을 더해주면 된다. 4개 + 2개 = 6개