Change

해당 문제는 여기에서 확인하실 수 있습니다

문제를 해결하기 위해서는 동적 프로그래밍을 활용하여 특정 금액을 만들 수 있는 경우의 수를 효율적으로 계산해야 합니다. 이 문제에서 목표는 n원을 거슬러 줄 수 있는 모든 방법의 수를 구하는 것입니다. 각 화폐 단위를 사용하여 금액을 만드는 방법을 조합해야 하며, 중복 계산을 피하기 위해 DP 배열을 사용합니다.

우선, 주어진 화폐 단위를 오름차순으로 정렬하여 작은 화폐 단위부터 계산을 시작합니다. 이렇게 하면 작은 화폐 단위를 먼저 고려한 뒤, 그 결과를 기반으로 큰 화폐 단위의 경우의 수를 계산할 수 있습니다. 이를 위해 배열 dp[i]를 정의하며, dp[i]는 i원을 만들 수 있는 경우의 수를 나타냅니다.

초기값으로 dp[0]을 1로 설정합니다. 이는 0원을 만드는 방법이 아무 화폐도 사용하지 않는 1가지 경우뿐이라는 것을 의미합니다. 이후, 각 화폐 단위에 대해 해당 화폐로 만들 수 있는 금액을 순차적으로 계산합니다. 이 과정에서, 현재 금액에서 해당 화폐 단위를 뺀 금액의 경우의 수를 dp[i]에 더하는 방식으로 경우의 수를 갱신합니다.

계산 과정에서 결과가 매우 커질 수 있으므로, 모든 연산에서 1,000,000,007로 나눈 나머지를 사용해 값이 초과하지 않도록 합니다. 최종적으로 dp[n] 값이 우리가 찾는 정답이 됩니다.

import java.util.Arrays;

class Solution {
  public int solution(int n, int[] money) {
    // 나머지를 계산하기 위한 상수
    final int MOD = 1_000_000_007;

    // 화폐 단위를 오름차순으로 정렬
    Arrays.sort(money);

    // dp[i]: i원을 만들 수 있는 경우의 수
    int[] dp = new int[n + 1];

    // 0원을 만드는 방법은 1가지 (아무것도 사용하지 않음)
    dp[0] = 1;

    // 각 화폐 단위에 대해
    for (int coin : money) {
      // 해당 화폐로 만들 수 있는 금액 갱신
      for (int i = coin; i <= n; i++) {
        // 이전 경우의 수를 더하고 MOD로 나눔
        dp[i] = (dp[i] + dp[i - coin]) % MOD;
      }
    }

    // n원을 만드는 방법의 수 반환
    return dp[n];
  }
}