동전 0

동전 0

문제 설명

준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다.

동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오.

예제 입력

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

예제 출력

6

---

문제 풀이

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

const solution = (input) => {
  let [N, K] = input.shift().split(" ").map(Number);
  // 동전 내림차순으로 정렬
  const coins = input.map(Number).sort((a, b) => b - a);
  let cnt = 0;
  for (let coin of coins) {
    // 카운트에 금액이 높은 순서부터 몫을 구한 후 누적
    cnt += Math.floor(K / coin);
    // K 는 동전의 몫을 구한 나머지로 바꿔주기
    K = K % coin;
  }

  console.log(cnt)
};
solution(input);

아이디어 / 접근법

1. 내림차순 정렬
2. 높은 동전부터 K에서 나올 수 있는 몫 계산
3. K 값 현재 동전에서의 나머지 값으로 재할당
4. 카운트 리턴

후기

그리디 문제였고 오랜만에 그리디 풀어봤는데 생각보다 어려웠음 아침에 머리 안돌아갈 때 풀어서 그런 지는 몰라도 뭔가 잘 안된 것 같았음