백준 11407: 동전 - javascript (그리디)

문제 출처 

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

문제

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

예제 입력 2 복사

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

문제 풀이 힌트 

- 주어진 동전들을 내림차순으로 정렬한다. 

- 예제 1번 같은 경우 

1
5
10
50
100
500
1000
5000
10000
50000

=> 50000,10000,5000,1000,500,100,50,10,5,1 이렇게 정렬된다. 

- 주어진 가격 4200원 보다 작은 돈 일 때 동전을 쓸 수 있다 !!

- 4200 > 1000 이니까 1000원을 활용해서 4개를 쓴다 => 4000원 

- 제시된 4790원 에서 활용한 4000원을 뺀다 => 790원 [동전 4개 씀] 

- 다시 반복문을 활용해서 790원 > 500원 일 때 500원을 활용해서 동전 1개를 쓴다 => 500원 

- 790원에서 활용한 500원을 뺀다 => 290원 [동전 4개 + 1개 씀]

... 이런식으로 풀어나간다 ~~ 

문제 풀이 코드 

const fs = require('fs');
let [N, ...nums] = fs.readFileSync('dev/stdin').toString().trim().split(/\s+/).map(Number);

let price = nums.shift();
nums.sort((a, b) => b - a);

let count = 0;

for (let i = 0; i < N; i++) {
  if (price < nums[i]) {
    continue;
  } else {
    const value = Math.floor(price / nums[i]);
    price -= value * nums[i];
    count += value;

    if (price === 0) {
      break;
    }
  }
}

console.log(count);

의사 코드 추가

const fs = require('fs');
let [N, ...nums] = fs.readFileSync('dev/stdin').toString().trim().split(/\s+/).map(Number);

let price = nums.shift();
nums.sort((a, b) => b - a); //내림차순으로 정렬한다.

let count = 0;

for (let i = 0; i < N; i++) {
  if (price < nums[i]) { //현재 가격이 더 작으면 패스~
    continue;
  } else {
    const value = Math.floor(price / nums[i]);
    price -= value * nums[i]; //가격에서 빼준다. 
    count += value; // 동전 몇개 썼는지 추가

    if (price === 0) {
      break;
    }
  }
}

console.log(count);