[알고리즘] 백준 11047 동전 0

문제설명

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

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

 

입력

첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000)

둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수)

 

출력

첫째 줄에 K원을 만드는데 필요한 동전 개수의 최솟값을 출력한다.

 

예제입력 1

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

 

예제출력 1

6

 

 

 

나의 첫 풀이

let fs = require('fs')
let input = fs.readFileSync('/dev/stdin').toString().trim().split('\n')
let [N, goal] = input[0].split(' ').map(Number);
const array = input.slice(1).map(Number);
let count = 0;


for(let i = N-1; i>=0; i--){
    while(array[i]<=goal){
   goal -= array[i];
   count++;
   }
    
    if (goal === 0) {
        break;
    }
}

console.log(count)

 

나는 너무 단순하게 생각했다.

 

일단 동전은 오름차순으로 주어진다고 했으니, 큰 동전을 먼저 사용해야 사용하는 동전 수가 적을테니 배열의 뒤에서 부터 반복문을 시작했다.

 

그리고 목표 금액보다 작은 금액이 나왔을 때, 목표금액 - 현재동전 을  가능할때까지 또한번 반복문을 사용했다.

 

그리고 혹시 목표금액이 음수가 될 수 있으니 goal이 0이 되면 바로 break했다.

 

하지만 이 문제는 이중for문을 사용할 만큼의 문제가 아니였다. 

 

다시 푼 코드를 확인해보자.

 

다른사람  코드 참고해서 푼 코드

let fs = require('fs')
let input = fs.readFileSync('/dev/stdin').toString().trim().split('\n')
let [N, goal] = input[0].split(' ').map(Number);
const array = input.slice(1).map(Number);
const sortedArray = array.sort((a,b)=> b - a)
let count = 0;

sortedArray.forEach((currentCoin)=>{
    if(currentCoin<=goal){
    count = count + Math.floor(goal/currentCoin)
    goal = goal%currentCoin
    }
})
console.log(count)

 

이번에는 한 번씩 제외하지 않고, 한번에 나누기로 동전 개수를 구한다음, 나눠지지 않는 몫을 goal에 할당하는 방식을 택했다.

 

내 첫 풀이는 반복문 안에 반복문이 있어서 시간복잡도 면에서도 굉장히 좋지 않았는데 이 코드는 매우 빠르게 동작하였다.