이 글에서는 하나의 자연수를 자신보다 작은 수들의 합으로 표현하는 방법이 총 몇 가지인지 구하는 C++ 프로그램을 다룹니다. 이는 조합론에서 말하는 분할(partition)의 개수를 세는 문제와 같습니다. 예를 들어 4는 3+1, 2+2, 2+1+1, 1+1+1+1의 네 가지 방법으로 표현할 수 있습니다.
프로그램의 동작 방식은 다음과 같습니다. 숫자 n을 입력받으면 n 자체를 첫 번째 분할로 놓고, 뒤쪽 요소부터 1씩 줄여가며 새로운 분할을 만들어 냅니다. 새로운 분할이 하나 생성될 때마다 카운터를 증가시키고, 모든 요소가 1로 분해되면 반복을 종료한 뒤 카운터 값을 반환합니다.
알고리즘
partitionCount(n)
입력 : 숫자 n
출력 : 분할의 개수
시작
크기가 n인 배열 p 생성
k := 0, count := -1
배열 p의 첫 번째 요소에 n 저장
다음 과정을 반복:
count를 1 증가
rem := 0
(k ≥ 0 이고 p[k] = 1)인 동안:
rem := rem + p[k]
k를 1 감소
만약 k < 0 이면:
count를 반환
p[k] := p[k] − 1
rem := rem + 1
(rem > p[k])인 동안:
p[k+1] := p[k]
rem := rem − p[k]
k를 1 증가
p[k+1] := rem
k를 1 증가
종료
예제 코드
#include<iostream>
using namespace std;
int partitionCount(int n){ // 가능한 모든 분할의 개수를 세는 함수
int p[n], k = 0, count = -1;
p[k] = n; // 배열의 첫 번째 요소로 n을 저장
while(true) { // 모든 요소가 1이 될 때까지 반복
count++;
int rem = 0;
while (k >= 0 && p[k] == 1){ // p[k] > 1인 위치로 포인터 이동
rem += p[k];
k--;
}
if (k < 0) // k < 0이면 모든 요소가 1로 분해된 상태
return count;
// 그렇지 않으면 현재 값을 1 줄이고 rem을 1 증가
p[k]--;
rem++;
while (rem > p[k]) { // 남은 값(rem)이 p[k]보다 작아질 때까지 반복
p[k+1] = p[k];
rem -= p[k]; // rem 값 감소
k++;
}
p[k+1] = rem; // 남은 값을 k 바로 다음 인덱스에 저장
k++;
}
}
main() {
int n, c;
cout<<"분할 개수를 셀 숫자 입력: ";
cin>>n;
if (n <= 0) { // n은 1 이상이어야 함
cout<<"잘못된 n 값";
exit(1);
}
c = partitionCount(n);
cout<<"분할의 개수: "<<c;
}
실행 결과
분할 개수를 셀 숫자 입력: 7 분할의 개수: 14
동작 원리 살펴보기
n = 7일 때 결과가 14가 나오는 이유를 살펴보겠습니다. 7의 전체 분할 개수는 15개이지만, 그중 7 자신 하나만으로 이루어진 분할은 '자신보다 작은 수들의 합'에 해당하지 않으므로 제외됩니다. 따라서 6+1, 5+2, 5+1+1, 4+3, 4+2+1, 4+1+1+1, 3+3+1, 3+2+2, 3+2+1+1, 3+1+1+1+1, 2+2+2+1, 2+2+1+1+1, 2+1+1+1+1+1, 1+1+1+1+1+1+1의 14가지가 카운트됩니다.
알고리즘 내부에서는 배열 p에 현재 분할 상태를 저장하고, 맨 뒤에서부터 값이 1보다 큰 요소를 찾아 1을 줄인 뒤, 남은 값(rem)을 오른쪽 요소들에 최대한 균등하게 배분하는 방식으로 다음 분할을 생성합니다. 이 과정을 모든 요소가 1이 될 때까지 반복하면 중복 없이 모든 분할을 한 번씩 얻을 수 있습니다.
참고 사항
예제 코드의 int p[n]은 가변 길이 배열(VLA)로, GCC 등 일부 컴파일러에서만 지원되며 C++ 표준은 아닙니다. 표준을 준수하려면 vector<int> p(n)을 사용하는 것이 좋습니다. 또한 실행 시간이 분할 개수에 비례해 늘어나므로, n이 큰 경우에는 동적 계획법(DP)으로 분할 개수를 구하는 편이 훨씬 효율적입니다.