🔥 Algorithm/Baekjoon
[백준 11047번] 동전 0 - 자바스크립트(nodejs)
Lennon
2022. 1. 23. 16:28
728x90
반응형
https://www.acmicpc.net/problem/11047
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해주면 끝!
728x90
반응형