문제 개요
서로 다른 액면가를 가진 동전들과 하나의 목표 금액이 주어졌을 때, 그 금액을 만들 수 있는 조합(combination)의 개수를 계산하는 함수를 작성해야 합니다. 이때 각 종류의 동전은 무한개 있다고 가정합니다.
예를 들어 목표 금액이 5이고 동전의 액면가가 [1, 2, 5]라면, 다음과 같이 총 네 가지 조합이 존재합니다.
(1+1+1+1+1), (1+1+1+2), (1+2+2), (5)
풀이 접근 방식 (동적 계획법)
이 문제는 대표적인 동적 계획법(DP) 유형입니다. 핵심은 바깥쪽 루프를 동전 종류 기준으로 돌려야 순서만 다른 경우(순열)가 아니라 진짜 '조합'만 세어진다는 점입니다. 풀이 과정은 다음과 같습니다.
- 크기가 amount + 1인 배열 dp를 생성합니다. dp[i]는 '금액 i를 만드는 조합의 수'를 의미합니다.
- dp[0] = 1로 초기화합니다. (금액 0을 만드는 방법은 어떤 동전도 사용하지 않는 딱 한 가지이므로)
- n := coins 배열의 크기
- 바깥 루프: i를 0부터 n-1까지 반복하며 각 동전 종류를 순회합니다.
- 안쪽 루프: j를 coins[i]부터 amount까지 반복합니다.
- dp[j] += dp[j - coins[i]] : 현재 동전 coins[i]를 추가했을 때 만들어지는 새로운 조합의 수를 누적합니다.
- 안쪽 루프: j를 coins[i]부터 amount까지 반복합니다.
- 최종적으로 dp[amount]를 반환합니다.
안쪽 루프가 j부터 시작하는 이유는, coins[i]보다 작은 금액에는 해당 동전을 사용할 수 없기 때문입니다.
C++ 구현 예제
아래 코드를 통해 더 자세히 이해해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int change(int amount, vector<int>& coins) {
vector <int> dp(amount + 1);
dp[0] = 1;
int n = coins.size();
for(int i = 0; i < n; i++){
for(int j = coins[i]; j <= amount; j++){
dp[j] += dp[j - coins[i]];
}
}
return dp[amount];
}
};
main(){
Solution ob;
vector<int> v = {1,2,5};
cout << (ob.change(5, v));
}입력
5 [1,2,5]
출력
4
복잡도 분석
시간 복잡도는 동전 종류의 수를 n, 목표 금액을 amount라고 할 때 O(n × amount)이며, 공간 복잡도는 DP 배열을 저장하기 위해 O(amount)입니다.