CoinChangeTopDownApproach 메서드는 총 4개의 매개변수를 받습니다. n은 만들어야 할 금액(amount)을 의미하고, coins 배열에는 해당 금액을 계산하는 데 사용할 수 있는 동전들의 종류가 담겨 있습니다. t는 동전의 총 개수이며, dp 배열은 한 번 계산된 값들을 저장하여 중복 연산을 방지하는 역할을 합니다.
동작 흐름은 다음과 같습니다. 먼저 금액이 0이면 더 이상 동전이 필요 없으므로 0을 반환합니다. 그다음 dp 배열에 이미 계산된 값이 있다면 재귀 호출 없이 즉시 해당 값을 반환하여 성능을 높입니다. 만약 아직 계산되지 않은 값이라면, 사용 가능한 각 동전을 하나씩 사용해 보며 CoinChangeTopDownApproach를 재귀적으로 호출한 뒤, 그중 최솟값을 선택해 dp 배열에 저장하고 반환합니다.
시간 및 공간 복잡도
- 시간 복잡도: O(N)
- 공간 복잡도: O(N)
예제 코드
public class DynamicProgramming{
public int CoinChangeTopDownApproach(int n,int[] coins,int t,int[] dp){
if (n == 0){
return 0;
}
if (dp[n] != 0){
return dp[n];
}
int ans = int.MaxValue;
for (int i = 0; i < t; i++){
if (n - coins[i] >= 0){
int subprob = CoinChangeTopDownApproach(n - coins[i], coins, t, dp);
ans = Math.Min(ans, subprob + 1);
}
}
dp[n] = ans;
return dp[n];
}
}
static void Main(string[] args){
DynamicProgramming dp = new DynamicProgramming();
int N = 15;
int[] coins = { 1, 7, 10 };
int[] dp1 = new int[100];
int t = coins.Count();
int res = dp.CoinChangeTopDownApproach(15, coins, t, dp1);
Console.WriteLine(res);
}실행 결과
3
위 예제에서는 목표 금액 15를 동전 {1, 7, 10}으로 만들 때, 최소 동전 개수는 3개(10 + 1 + ... 대신 10 + 4? 실제로는 10 + 1×5 → 6개가 아니라, 10 + 1 + 1 + 1 + 1 + 1이 아니라 7 + 7 + 1 = 15로 3개)임을 확인할 수 있습니다. 이처럼 하향식 메모이제이션(Memoization) 기법을 활용하면 단순 재귀 방식에 비해 불필요한 중복 계산을 제거하여 효율적으로 문제를 해결할 수 있습니다.