[JavaScript] 백준 2294. 동전2

백준 링크

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

문제 접근

우선 가치 K를 완성하기 위해 필요한 최소 동전 개수를 구하기 위해

완전 탐색 방식으로 접근을 시도 했다.

그림 설명

가치는 K이고 동전은 [1,2,3,4....N] 가정했을 때,

Top Down 방식으로 생각한다면, 가치 K가 되기 위해서는 K-1, K-2, K-3, .....K-N 에서 동전 한개를 추가했을 것이다.

따라서 트리형식이고, 이 경우의 시간복잡도는 O(N^K)이 된다.

그리고 시간 초과가 된다.

 

따라서 다른 방식을 생각해내야 했다.

 

그렇다면 DP는 어떨까?

 

가치 K가 되기 위해서는 dp[K-coin] + 1 과 dp[K] 의 최소값을 넣어주면 될것같았다.

 

이중 반복문을 사용하여,

첫번째 반복문 -> 모든 코인에 대해 순회

두번째 반복문 -> 가치에 대하여, 가치 = 해당 코인 ~ 최종 가치 K일 때까지 순회하면서 반복하면

작은 동전일 경우부터 차례대로 dp가 업데이트 될것이라고 생각했다.

 

✅ DP

문제 풀이 

dp 배열

- dp[i]는 가치가 i를 만들 수 있는 가장 적은 동전의수를 의미한다.

- 우선 dp[0] = 0으로 초기화한다.

 

점화식

👉 dp[curVal] = min(dp[curVal - coin] + 1, dp[curVal])

- 현재 가치(curVal)까지의 최소 동전 개수는

  - dp[현재 가치  - 코인 가치] + 1 혹은 dp[현재 가치]이다.

 

dp[현재 가치 - 코인 가치] + 1 의미

- 예를 들어 3이라는 가치를 만들기 위해 코인이 [1,2]가 있다고 가정하자.

 

코인 가치 1인 동전에 대해서

- 그럼 dp[3] 은 dp[2] + 1일 것이다. -> 가치가 2일 때의 최소 동전 개수 + 1

 

다음으로 코인 가치 2인 동전에 대해서

- dp[3] = dp[1] + 1이다. 

- 추가적으로 이전 코인 가치 1일 때와 비교해서 더 적은 수를 dp[3]에 최종적으로 저장하면 된다.

 

const fs = require("fs");
const input = fs.readFileSync("/dev/stdin", "utf8").trim().split("\n");

const [N, K] = input[0].split(" ").map(Number);
const coins = input.slice(1, N + 1).map(Number);

const dp = Array(K + 1).fill(Infinity);
dp[0] = 0;

coins.forEach((coin) => {
  for (let curVal = coin; curVal <= K; curVal++) {
    dp[curVal] = Math.min(dp[curVal - coin] + 1, dp[curVal]);
  }
});

console.log(dp[K] === Infinity ? -1 : dp[K]);

 

코드 예시

예를 들어, 동전이 [2, 5]이고 K= 7인 경우,

초기: [0, Inf, Inf, Inf, Inf, Inf, Inf, Inf]

2원 동전 처리 후:
[0, Inf, 1, Inf, 2, Inf, 3, Inf]

5원 동전 처리 후:
[0, Inf, 1, Inf, 2, 1, 3, 2]

 

❌ DFS 문제 풀이 - 시간초과

const fs = require("fs");
const input = fs.readFileSync("/dev/stdin", "utf8").trim().split("\n");

const [N, K] = input[0].split(" ").map(Number);
const sortOfCoins = input.slice(1, N + 1).map(Number);

let answer = Infinity;

function dfs(totalValue, numOfCoins) {
  if (totalValue === 0) {
    answer = Math.min(numOfCoins, answer);
    return;
  }

  sortOfCoins.forEach((coin) => {
    if (totalValue - coin >= 0) {
      dfs(totalValue - coin, numOfCoins + 1);
    }
  });
}

dfs(K, 0);
console.log(answer);