백준 - 동전 0(11047번)

백준 - 동전 0(11047번)

문제

• 준규가 가지고 있는 동전은 총 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. 동전의 가짓수를 N으로 입력받는다.
2. 금액을 K로 입력받는다.
3. N만큼 반복하며 K를 각 금액으로 나눈 값을 합하고, K에 나머지를 저장하여 다시 반복한다.

---

제출한 답

const input = require("fs")
  .readFileSync(process.platform === "linux" ? "/dev/stdin" : "./input.txt")
  .toString()
  .trim()
  .split("\n")
  .map((el) => el.split(" ").map(Number));


  const N = input[0][0];
  let K = input[0][1];

  let num = 0;
  for(let i=N; i>0; i--){
    if(K === 0)
        break;
    if(K >= input[i][0]){
        num += Math.floor(K/input[i][0]);
        K %= input[i][0];
    }
  }

  console.log(num);

---

Js로 백준 풀기

이전 문제 풀이에서 언급했듯이 Js로 백준을 푸는 것은 꽤나 까다롭다. 그래서 계속 피해왔지만 그래도 풀어야한다. 이 글을 참고해서 문제를 풀었다. 혹시 Js로 문제풀이를 할 경우 참고하시길 바란다.

간략하게 설명하자면

const input = require("fs")
  .readFileSync(process.platform === "linux" ? "/dev/stdin" : "./input.txt")
  .toString()
  .trim()
  .split("\n")
  .map((el) => el.split(" ").map(Number));

백준은 리눅스 환경에서 실행된다. VSCode에서 실행을 위해 삼항연산자를 활용하여 input.txt 파일을 동일 디렉토리에 저장해 사용한다.

.toString()을 사용하여 입력값을 문자열로 받고, .trim()으로 공백을 제거한 후, .split("\n")으로 줄바꿈을 기준으로 문자열을 나눈다. .map()은 새로운 배열을 반환해주는 함수이다.

예를들어 해당 문제에서 입력이 아래와 같은 형식으로 들어온다.

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

1. .toString()으로 해당 입력값들을 문자열로 변환한다.
2. .trim()으로 혹시 모를 공백을 제거한다.
3. .split("\n")으로 배열을 생성한다.

   [
     "10 4200",
     "1",
     "5",
     "10",
     "50",
     "100",
     "500",
     "1000",
     "5000",
     "10000",
     "50000"
   ]

4. .map()으로 각 문자열을 공백을 기준으로 분리하고 숫자로 변환한다.

   [
     [10, 4200],
     [1],
     [5],
     [10],
     [50],
     [100],
     [500],
     [1000],
     [5000],
     [10000],
     [50000]
   ]

기본적인 틀은 위와 같고 입력받는 값에 따라 잘 변환해서 사용하면 된다.

---

💡한줄평

역시 백준을 Js로 풀 때는 입력받는 것에 신경을 잘 써야하는 것이 번거롭고 어렵다. 이 부분으로 인해 두 번이나 오답이 발생했다. 더 익숙해지도록 노력해야겠다.