[백준 node.js] 11047번_동전 0

백준 그리디 알고리즘 11047번_동전 0

난이도 : 실버 I

 

문제 설명

입출력

 

문제 풀이 : 그리디의 대표 유형 문제 중 하나이다. 주어진 돈을 화폐에 맞게 최소 개수를 구하면된다.

주어진 화폐를 큰 순서대로 돈이랑 비교한다.

주어진 돈이 화폐보다 더 클시 나누어 떨어질 수 있으니깐 돈/화폐의 몫을 카운트를 해주고

나머지를 주어진 돈으로 교체해줍니다. 이런식으로 가지고 있는 돈과 화폐를 차례로 나누어주면서 

최솟값을 구할 수 있다.

 

function solution(n, k, list) {
    let count = 0;

    for(let i of list) {
        if(k === 0){
            break;
        }
        if(k >= i){
            count += parseInt(k / i);
            k = k % i;
        }
    }
   console.log(count);
  
}

const readline = require("readline");
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout,
});

let input = [];
rl.on("line", function (line) {
    //여러줄 입력
    input.push(line)
}).on("close", function () {

    //tmp에 n, k 저장
    let tmp = input[0].split(' ').map((el) => parseInt(el));
   
    //화폐단위 list에 저장
    let list = input.slice(1);
    //map을 이용하여 INT형으로 바꿈
    list = list.map((el)=> parseInt(el));
    //큰 화폐부터 계산 역순
    list.reverse();
    solution(tmp[0], tmp[1], list);
    process.exit();
});

 

* 진짜 node.js의 입력 처리는 매우 귀찮다.... 파이썬과 자바와 달리 한번에 모든 값을 받아와 처리해줘야하기 때문에

매우 귀찮은 작업이 필요하다 ㅠㅠ