[JS][백준]2294_동전 2

문제 번호

2294번: 동전 2

 

 

알고리즘 분류

• 다이나믹 프로그래밍

 

문제 풀이

 DP를 접할 때 거의 무조건 만나 볼 수밖에 없는 동전 문제이다. 여러 가지 형태의 동전 문제가 있지만 '동전 2'는 k원을 최소 개수의 동전을 사용해서 만들어야 한다.

 

 이때 k원을 만들기 위해서 필요한 동전의 최소 개수를 저장하기 위해서 dp라는 배열을 사용하였다. k원 까지 만들어야 하니까 dp배열의 크기는 k+1이다.(0원도 생각해야 한다) 그리고 0원을 만드는 최소 개수는 당연히 0개이다.

  let dp = new Array(k + 1).fill(Infinity);
  dp[0] = 0;

 이제 dp[j]에 대해서 생각해본다. dp[j]는 j원을 만드는데 필요한 동전의 최소 개수이다. 주어진 n개의 동전을 차례로 살펴보자. i번째 동전이 마지막으로 오면서 j원을 만드는 경우를 생각해본다. i번째 동전이 마지막으로 와서 j원을 완성시키기 때문에 dp[j-coin[i]]원의 개수에 i번째 동전(1개)을 추가시켜야 한다. 혹은 i번째 동전이 마지막으로 오는 경우가 최소 개수가 아닐 수 도 있다. 둘 중 더 적은 동전을 사용하는 경우를 dp[j]로 한다. 

      dp[j] = Math.min(dp[j], dp[j - coins[i]] + 1);

 이해가 잘 가지 않을때는 손으로 직접 따라서 해보는 것이 제일 좋다. 문제에서 주어진 예시는 동전의 종류도 3개뿐이라 금방 할 수 있었다.

 

 마지막으로 불가능할 경우 -1을 출력하는것을 잊지 않는다.

  // 불가능한 경우에는 -1 이다.
  for (let i = 0; i < dp.length; i++) {
    if (dp[i] == Infinity)
      dp[i] = -1;
  }

전체 코드

/**
 * k원. 최소 갯수.
 * dp[i] : i원을 만들때 최소로 사용한 동전의 개수. 
 * 2중 for문을 사용한다. i,j
 * dp[j] : i번째 동전을 마지막으로 할때, j원을 만드는 가장 적은 동전의 수. 
 */
function main() {
  let answer = -1;
  const input = require('fs').readFileSync('input.txt').toString().trim().split('\n')
  const [n, k] = input[0].trim().split(' ').map(Number);
  const coins = input.slice(1).map(_ => +_.trim());
  answer = sol(n, k, coins);

  return console.log(answer);
}
function sol(n, k, coins) {
  let dp = new Array(k + 1).fill(Infinity);
  dp[0] = 0;

  // 최소 동전 개수로 k원을 만들어보자. O(10^6)
  for (let i = 0; i <= coins.length; i++) { // 목표로 하는 금액. max 100
    for (let j = coins[i]; j <= k; j++) {  //max 10000
      dp[j] = Math.min(dp[j], dp[j - coins[i]] + 1);
    }
  }
  // 불가능한 경우에는 -1 이다.
  for (let i = 0; i < dp.length; i++) {
    if (dp[i] == Infinity)
      dp[i] = -1;
  }
  return dp[k];
}
main();

특이사항

 처음 풀어본 문제는 아니었다. 그러나 풀 때마다 정답이나 힌트를 참고했었는데 시간이 지나고 나서 이번에 풀어봤을 땐 힌트를 참고하지 않고도 풀 수 있었다. 다른 종류의 동전 문제도 풀어봐야 한다.