[알고리즘/javascript] 백준 11047번: 동전 0

문제 바로가기

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

✏️ Problem

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

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

 

[ 예제 입출력 ]

🧑‍💻 Solution

[ 설계 ]

예제 1을 통해 문제를 살펴보자.

준규가 가지고 있는 동전은 [1, 5, 10, 50, 100, 500, 1000, 5000, 10000, 50000] 이다.

이 동전들을 사용해 4200원을 만들 수 있는 동전 개수의 최솟값을 구해야 한다.

 

쉽게 구하기 위해 동전 배열을 내림차순으로 정렬해준다.

동전 배열을 순회하면서 만약 요소가 금액(K)보다 작을 경우 다음 요소로 건너뛴다.

K를 동전 요소를 나눈 몫을 구하고 K를 나머지 값으로 변경한다. 그리고 정답수(answer)에 몫만큼을 더해준다.

 

예제 1의 4200원으로 시작해보자.

내림차순으로 정렬된 동전 배열은 50000부터 시작되지만, 50000, 10000, 5000은 4200보다 크기 때문에 건너뛴다.

1000 차례가 되면 value 값은 Math.floor(4200 / 1000) = 4가 된다. 1000원 짜리 4장이 필요하다는 의미이다.

K는 4200 % 1000인 200으로 변경되고 answer은 4가 된다.

다음 요소로 500이 들어가지만 500은 K인 200보다 크기 때문에 건너뛴다.

다음으로 100이 들어가고 value는 Math.floor(200/100) = 2가 된다. 100원 짜리 2개가 필요하다는 의미이다.

K는 200 % 100인 0이 되고 answer은 4에 2를 더한 6이 된다. K가 0이 되어 반복문이 종료된다.

 

[ 작성 코드 ]

let [info, ...coinArr] = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n');
let [N, K] = info.split(' ').map(Number);
coinArr = coinArr.map(Number).sort((a, b) => b - a);

let answer = 0;

for(let i = 0; i < N; i++) {
    if(K < coinArr[i]) {
        continue;
    } else {
        const value = Math.floor(K / coinArr[i]);
        K = K % coinArr[i];
        answer += value;
        
        if(K === 0) break;
    }
}

console.log(answer)