백준 11047번 Node.js 문제 풀이

문제 링크

- 내 풀이

const fs = require("fs");
const input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");

let [N, K] = input.shift().split(" ").map(Number);

const coinArr = input.map(Number);

let answer = 0;

for (let i = coinArr.length - 1; i >= 0; i--) {
  const coin = coinArr[i];

  if (coin > K) {
    continue;
  }

  const amount = Math.floor(K / coin);

  answer += amount;

  K -= amount * coin;
}

console.log(answer);

대표적인 그리디 알고리즘 문제이다.

각 화폐의 단위는 서로 배수 관계 에 해당한다.

가장 큰 화폐부터 나누어주면서, 해당 값들을 정답에 누적시켜주면 된다

왜 가장 큰 화폐부터 나누어주면 되는가 ?

위에서 각 화폐의 단위는 서로 배수 관계에 있다고 했는데, 이말인 즉슨

가치가 큰 동전은 가치가 작은 동전들의 합으로 표현이 될 수 있기 때문이다.

생각해보면 저 반복문 안에 있는 if 문은 없어도 되는것 같다.