[실버] 동전 0 (11047번)_JS

문제

준규가 가지고 있는 동전은 총 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 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수)

이걸 발견을 못하고 고민고민을 하다가 발견하곤 바로 탐욕법(그리디)을 시도했다. 

탐욕법은 지금 제일 좋은 걸 시도해보는건데,

지금 상황에서 동전의 가치가 잡다했으면 시도할 수 없다.

다행히 가치가 배수로 늘어나 가능했다.

 

[첫 번째 코드]

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "input.txt";
let input = fs.readFileSync(filePath).toString().trim().split("\n");
const [N, K] = input.shift().split(" ").map(Number);
input = input.sort((a, b) => b - a).map(Number);

let result = 0;
let valMoney = K;

for (let i = 0; i < input.length; i) {
    if (input[i] <= valMoney) {
        result++
        valMoney -= input[i]
    } else {
        i++
    }
}

console.log(result);

나는 동전 가치가 내림차순인게 편해서 이렇게 바꾸었다.

넣고 넣고 넣고.. 다 K가 될 때까지 넣게 만들었다.

 

그 결과,,, 속도가 400대가 나왔다..

남들은 100에도 나오는걸..

그래서 참고하여 다시 짜봤다.

 

[두 번째 코드]

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "input.txt";
let input = fs.readFileSync(filePath).toString().trim().split("\n");
const [N, K] = input.shift().split(" ").map(Number);
input = input.sort((a, b) => b - a).map(Number);

let result = 0;
let valMoney = K;

for (let i = 0; i < input.length; i) {
    if (input[i] <= valMoney) {
        result += Math.floor(valMoney / input[i])
        valMoney = valMoney % input[i];
    } else {
        i++
    }
}

console.log(result);

 

여기서 포인트는 만약 가치단위가 목표가치 안에 포함되면

하나하나 넣어보는 것이 아니라 아예 나눠서 계산 횟수를 단축하는 것이다.

 

예로 9000이 목표 가치이고 1000단위이면,

1000단위가 들어간다는 것을 확인 후

1000을 9번 넣는 것이 아니라

그냥 1000으로 나누어주고 그 몫인 9를 count에 더해주는 것이다.

 

그 결과 속도가 훨씬 줄었다.

코드를 돌리는 것만이 아니라 계산을 줄이고 속도를 빠르게 하는 법을 생각하자