[BOJ 9084] 동전

문제

동전

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

 

 

풀이

설명

동전의 종류가 주어질 때, 주어진 금액을 만드는 모든 방법을 구하는 문제입니다.

 

DP를 이용해 해결할 수 있습니다.

 

dp[i]는 금액 i를 만들 수 있는 방법의 수입니다.

동전 종류와 개수만 가지고 방법을 세므로 누적합을 이용할 수 있습니다.

dp[0] = 1로 초기화 해줍니다.

 

동전 종류가 coin이라고 한다면, i원을 만들 수 있는 방법의 수는 다음과 같습니다.

이전까지의 동전 종류로 민들 수 있는 방법의 수 + (i - coin)원을 만들 수 있는 방법의 수입니다.

따라서 dp[i] = dp[i] + dp[i - coin]입니다.

 

예시 코드

function solution() {
  const T = Number(input());
  const answer = [];

  for (let tc = 0; tc < T; tc++) {
    const N = Number(input());
    const coins = input().split(" ").map(Number);
    const M = Number(input());
    // dp[i] = 금액 i를 만들 수 있는 방법의 수
    const dp = Array(M + 1).fill(0);
    dp[0] = 1;

    for (const coin of coins) {
      for (let i = coin; i <= M; i++) {
        dp[i] += dp[i - coin];
      }
    }
    answer.push(dp[M]);
  }

  return answer.join("\n");
}