# [Algorithm/JS] 백준 11047번 동전 0

🔗 문제 바로가기 (opens new window)

# Question

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

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

# Input

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

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

# Output

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

# Example

# Input 1

1
2
3
4
5
6
7
8
9
10
11

# Output 1

# Input 2

1
2
3
4
5
6
7
8
9
10
11

# Output 2

# Solution

const fs = require('fs');
const [N, K, ...coins] = fs.readFileSync('dev/stdin').toString().split(/\s+/).map(Number);
coins.sort((a, b) => b - a); // 1

let cnt = 0;
let price = K;

for (let i = 0; i < N; i++) {
  if (price >= coins[i]) {
    // 2
    cnt += Math.floor(price / coins[i]); // 3
    price -= coins[i] * Math.floor(price / coins[i]); // 4

    if (price === 0) break; // 5
  }
}

console.log(cnt);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

최소의 동전 개수를 구해야하기 때문에 각 동전의 가치를 내림차순으로 정렬한다.
가치가 가격보다 낮은 동전일 때만 코드를 실행한다.
Math.floor(price / coins[i]) 는 해당 동전을 사용할 수 있는 개수이다. 개수만큼 cnt 를 증가시킨다.
가격을 동전의 개수 * 동전의 가치 만큼 뺀다.
가격이 0이 된다면 반복문을 벗어난다.

← 15649번 N과 M (1) 1931번 회의실 배정 →