이 문제에서는 정수 배열과 숫자 N이 주어지며, 배열의 요소들을 더하여 N을 만들 수 있는 총 경우의 수를 구하는 것이 목표입니다. 이때 모든 조합과 중복 사용이 허용됩니다.
예시를 통해 문제를 자세히 살펴보겠습니다.
입력
arr = {1, 3, 5} N = 6출력
8
설명
N = 6을 만들 수 있는 방법은 다음과 같습니다.
5+1, 1+5, 3+3, 3+1+1+1, 1+3+1+1, 1+1+3+1, 1+1+1+3, 1+1+1+1+1+1
위 예시에서 볼 수 있듯이, 요소가 등장하는 순서가 다르면 서로 다른 조합으로 간주합니다. 예를 들어 4개의 요소로 합을 만드는 경우, 순서만 다른 4가지 방법을 각각 별개의 경우로 계산합니다.
이러한 유형의 문제는 단순 반복문으로는 해결하기 어렵기 때문에 동적 계획법(Dynamic Programming)을 활용하는 것이 효과적입니다. 핵심 아이디어는 다음과 같습니다.
- dp[i]를 '배열 요소들의 합으로 i를 만드는 방법의 수'로 정의합니다.
- 초기값으로 dp[0] = 1을 설정합니다. 이는 합이 0인 경우(아무것도 선택하지 않는 경우)를 한 가지로 보기 위함입니다.
- 각 금액 i에 대해 배열의 모든 요소 j를 검토하며, i가 array[j]보다 크거나 같으면 dp[i] += dp[i - array[j]] 점화식을 적용합니다.
아래 프로그램은 이 알고리즘의 구현 예시입니다.
예제 코드
#include <iostream>
#include <cstring>
using namespace std;
int arraySumWays(int array[], int size, int N){
int count[N + 1];
memset(count, 0, sizeof(count));
count[0] = 1; // 합이 0인 경우는 1가지 (공집합)
for (int i = 1; i <= N; i++)
for (int j = 0; j < size; j++)
if (i >= array[j])
count[i] += count[i - array[j]];
return count[N];
}
int main() {
int array[] = {1, 5, 6};
int size = sizeof(array) / sizeof(array[0]);
int N = 7;
cout<<"Total number of ways in which "<<N<<" can be generated using sum of elements of array is "
<<arraySumWays(array, size, N);
return 0;
}출력 결과
Total number of ways in which 7 can be generated using sum of elements of array is 6
동작 원리 분석
배열 {1, 5, 6}으로 N = 7을 만드는 6가지 방법은 다음과 같습니다.
1+1+1+1+1+1+1, 1+1+5, 1+5+1, 5+1+1, 1+6, 6+1
이 알고리즘의 시간 복잡도는 O(N × size)이며, 공간 복잡도는 O(N)입니다. N이 클 경우 VLA(가변 길이 배열) 대신 vector를 사용하면 더 안전하게 구현할 수 있습니다. 또한 동일한 로직은 '계단 오르기' 문제나 동전 교환 문제 등 다양한 조합론적 DP 문제에 응용할 수 있습니다.