[ 백준_2293 ] 동전 1 ( DP, by using JavaScript )

문제

 

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

2293번: 동전 1

 

 

How to Solve ?

 

DP를 이용해서 풀었는데, 이해가 꽤 어려워서 그림을 통해 설명 하고자 한다.

 

1) 1원

 

1원만 가지고 1 ~ 10원을 만드는 경우는 모두 1가지 밖에 없다

 

2) 2원

 

2원을 가지고 금액을 계산 하는 경우는 다음과 같다

 

2원 => 2원 (1)

2원 => 3원 ( 2원 + 1 )

2원 => 4원 ( 2+1+1, 2+2 )

2원 => 5원 ( 2+1+1+1, 2+2+1 )

 

아래의 그림을 보면 더욱 이해가 잘될텐데 2원에서 4원에 접근 할 때는

[ 1원에서 2원을 접근 하는 경우 + 2원에서 2원을 접근 하는 경우 ] 에다가 2원만 추가하면 됬기에 2가지 경우가 가능하다.

 

다음과 같이 반복을 하면 문제를 풀 수 있다.

 

뿐만 아니라, 나는 1차원 배열로 이용하였지만 그림을 2차원 배열로 그려서 이점을 감안 하면 좋을 것이다 !

function solution() {
  for (let i = 0; i < coins.length; i++) {
    for (let j = coins[i]; j <= target; j++) {
      dp[j] += dp[j - coins[i]];
    }
  }
  return dp[target];
}

let coins = [1, 2, 5];
let target = 10;
let dp = Array(target + 1).fill(0);
dp[0] = 1;
console.log(solution());