[백준] 2293 - 동전 1 (node.js)

문제

 

코드

let fs = require("fs");
// "/dev/stdin"
// "./text.txt"
let input = fs.readFileSync("./text.txt").toString().split("\n");

const [n, k] = input
  .shift()
  .split(" ")
  .filter((v) => v);

let coins = input.map((v) => +v);

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

coins.forEach((v) => {
  for (let j = v; j <= k; j++) {
    dp[j] += dp[j - v];
  }
});

console.log(dp[k]);

 

문제 해결 과정

저번 멘토링 받았던 것을 토대로 우선 문제를 풀기 전 시간 복잡도와 공간 복잡도를 생각해봤다. 

문제 조건이 1 <= n <= 100 이고, 1 <= k <= 10000 이므로 n개의 동전을 사용할 때/사용하지 않을 때를 나눠서 생각해본다면 2^100 이므로 2^10이 1024니까 1024^10정도! 그냥 엄청 크다. 그래서 완전탐색으로는 풀지 못한다고 결정지었다.

그리고 앞서 사용한 동전에 따라 현재 계산할 금액에 영향을 끼치므로 dp를 생각하게 되었다. 

 

문제 플이

 

우선 dp[0]=1을 설정해둔다. 0원을 만들기 위해서 아무런 동전을 사용하지 않는 경우 1가지가 있기 때문이다.

그리고 동전의 금액에 따라 1원부터 k원까지 만들 수 있는 경우의 수를 계산한다. 

즉, dp[k]는 k원을 만들 수 있는 경우의 수이다.

 

예제 입력으로 1원, 2원, 5원 동전이 주어졌을 때 우선 1원짜리 동전으로 k원을 만들 수 있는 경우의 수를 dp에 저장한다. 그리고 1원, 2원자리 동전으로 3원을 만들 수 있는 경우의 수는 아래와 같이 계산해주면 된다.

dp[3](1원,2원짜리 동전으로 표현한 경우의 수) = dp[3](기존 1원짜리 동전만으로 표현한 경우의 수) + dp[1] 

 

그래서 dp[j] += dp[j-v]의 의미는

v(현재 동전 금액)를 1개 사용했을 때 j-v원을 만드는 경우의수 (3원을 만들기 위해 2원짜리 동전 한개를 사용했을 때 1원을 만드는 경우의 수)를 더해준 것이다.

 

이것을 표로 표현해보자.

 

1원짜리 동전만 사용할 때

1	2	3	4	5	6	7	8	9	10
1	1	1	1	1	1	1	1	1	1

 

1원짜리, 2원짜리 동전을 사용할 때

1	2	3	4	5	6	7	8	9	10
1	2	2	3	3	4	4	5	5	6

 

1원짜리, 2원짜리, 5원짜리 동전을 사용할 때

1	2	3	4	5	6	7	8	9	10
1	2	2	3	4	5	6	7	8	10

 

문제점 및 느낀점

 

처음에는 node.js로 풀었는데 메모리초과가 계속 떠서 찾아보니 node.js로는 풀 수 없는 문제였었던 것 같다. 그래서 java로 풀어서 제출했다 ㅜ.ㅜ 그리고 dp 조건을 잡는데 시간이 꽤나 걸렸던 것 같다. 그래서 결국 풀이를 보게 되었는데 풀이도 이해하는데 시간이 좀 걸렸다. dp 문제는 많이 풀어봐야 익숙해질 것 같다 !!