BOJ - 11047 동전 0

문제 링크 : https://www.acmicpc.net/problem/11047

문제 티어 : 실버 4

문제 유형 : 그리디 알고리즘

문제 방법 

1) N, K 를 입력 받는다. 

2) 이미 오름차순으로 주어지고 있다. 그러나 우리는 동전 갯수를 최소로 써야 하기 때문에 역순으로 먼저 써야 한다.

3) 만약 동전의 가치가 K보다 크면 그냥 skip 하고 K보다 작으면 몫만큼 동전의 갯수로 더해준다. ( 4200 / 1000 = 4개의 동전) 

4) 3) 과정에서 나온 나머지를 다시 3) 과정 반복 

5) 만약 위 과정을 반복한 나머지가 0이 되면 종료 후 동전의 갯수 출력

 

문제 코드 

const fs = require("fs");
let input = fs.readFileSync("/dev/stdin").toString().split("\n");
// 첫째 줄에 두 개의 값 입력 받음
let [N,K] = input[0].split(" ").map(Number);
let arr = [];
// N 만큼 입력 받기 
for(let i=1;i<=N;i++){
    arr.push(Number(input[i]));
 }
 
 // arr 역순으로 반복문 돌림 
 let count = 0;
 
 for(let i=arr.length-1;i>=0;i--){
    
        count+=parseInt(K/arr[i]);
        K %= arr[i];
 }
 console.log(count);

 

1. 어차피 arr[i]이 K보다 크면 몫이 그대로 남으니깐 굳이 if문으로 필터링을 해줄 필요는 없었다.

2. 몫이 나누어 떨어지지 않을 수도 있으므로 parseInt로 정숫형으로 만들어줬다. 

3. 몫이 동전의 갯수가 되므로 몫 만큼 count에 더해줌

3. 그 후 나머지가 K가 되어야 하기 때문에 %한 값을 K로 만들어 준다.

 

 

시간복잡도 : O(N)