[JS] 그리디 알고리즘 (Greedy)

❗️ 그리디 알고리즘

• 선택의 순간마다 최적의 상황만을 쫓아 최종적인 해답에 도달하는 알고리즘
• 항상 최적의 결과를 보장하지는 않음

✅ 특징

• 최적의 결과를 구하는 알고리즘보다 빠름
• 크루스칼, 다익스트라 알고리즘 등에 사용
• 근사값을 구하는 알고리즘에 주로 사용

❗️동전0 - 백준 11047번

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

let dir = __dirname + "/11047.txt";
const path = process.platform === "linux" ? "./dev/stdin" : dir;
const input = require("fs").readFileSync(path).toString().trim().split("\n");

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

let coins = input.map(Number).sort((a, b) => b - a);
let idx = 0;
let count = 0;
while (true) {
  let tmp = Math.floor(K / coins[idx]);
  if (tmp === 0) {
    idx++;
    continue;
  }
  count += tmp;
  K = K - coins[idx] * tmp;
  idx++;
  if (K === 0) break;
}
console.log(count);