[백준 11047번] 동전 0 - 자바스크립트(nodejs)

https://www.acmicpc.net/problem/11047

11047번: 동전 0

const fs = require('fs');
let [N, ...nums] = fs.readFileSync('dev/stdin').toString().trim().split(/\s+/).map(Number);

let price = nums.shift();
nums.sort((a, b) => b - a);

let count = 0;

for (let i = 0; i < nums.length; i++) {
  if (price < nums[i]) {
    continue;
  } else {
    const value = Math.floor(price / nums[i]);
    price -= value * nums[i];
    count += value;

    if (price === 0) {
      break;
    }
  }
}

console.log(count);

그리디 알고리즘 문제이다. 최적의 방법을 찾아야 하므로 동전의 금액에 대해 내림차순으로 정렬한다.

그 후 배열을 순회하며 price보다 큰 동전들은 continue로 넘겨주고, 작은 값들이 나오면 최대 개수만큼 빼준다.

=> 가격이 4500원이고, 동전 list가 [5000,1000,500] 이면 5000은 넘기고, 1000에서 4번, 500에서 1번 해주는 게 최적의 방법이다.

 

price가 0이 되었을 때 반복문을 멈추고 count를 return해주면 끝!