이 문제에서는 하나의 정수 n이 주어지며, 우리의 과제는 이 수를 두 개 이상의 양의 정수의 합으로 표현할 수 있는 총 경우의 수를 구하는 것입니다.
예시를 통해 문제를 자세히 살펴보겠습니다.
입력
N = 4
출력
5
설명
4는 다음과 같은 방법으로 합을 표현할 수 있습니다. 4, 3+1, 2+2, 2+1+1, 1+1+1+1
즉, 4를 양의 정수의 합으로 나타내는 방법은 총 5가지입니다.
접근 방법: 오일러 점화식 활용
이 문제를 해결하기 위해 우리는 오일러(Euler)의 점화식을 사용합니다. 어떤 수 n에 대해 분할수 p(n), 즉 n을 양의 정수의 합으로 표현하는 방법의 총 개수는 다음과 같은 생성함수로 정의됩니다.
Σ∞n=0 p(n)xn = Π∞k=1 (1/(1-xk))
이 공식을 전개하면 p(n)을 계산하기 위한 점화식을 유도할 수 있습니다.
p(n) = p(n-1) + p(n-2) - p(n-5) - p(n-7) + … + (-1)(k-1)((k(3k-1))/2)
여기서 계수로 사용되는 1, 2, 5, 7, 12, 15… 는 오각수(pentagonal number)로, 일반항은 k(3k-1)/2입니다. 각 항의 부호는 두 개의 오각수마다 번갈아 가며 바뀌며, 이 패턴을 통해 동적 계획법(DP)으로 p(n)을 효율적으로 계산할 수 있습니다.
구현 예제
위 점화식을 C++로 구현한 프로그램은 다음과 같습니다.
예제 코드
#include <bits/stdc++.h>
using namespace std;
long long postiveSum(int n){
vector<long long> p(n + 1, 0);
p[0] = 1;
for (int i = 1; i <= n; ++i) {
int k = 1;
while ((k * (3 * k - 1)) / 2 <= i) {
p[i] += (k % 2 ? 1 : -1) * p[i - (k * (3 * k - 1)) / 2];
if (k > 0)
k *= -1;
else
k = 1 - k;
}
}
return p[n];
}
int main(){
int N = 12;
cout<<"The number of ways "<<N<<" can be written as sum of two or more positive numbers is " <<postiveSum(N);
return 0;
}출력 결과
The number of ways 12 can be written as sum of two or more positive numbers is 77
코드 설명
- 배열 p의 각 인덱스 i는 해당 숫자를 양의 정수의 합으로 표현하는 방법의 수를 저장합니다.
- p[0] = 1로 초기화하는 이유는 빈 합(공집합)을 하나의 경우로 간주해 점화식의 기저 조건으로 사용하기 위함입니다.
- 내부 반복문에서는 오각수 k(3k-1)/2가 현재 값 i보다 작거나 같은 동안 부호(+/-)를 교차 적용하며 p[i]를 누적합니다.
- k 값을 1, -1, 2, -2, 3, -3… 순으로 변환하여 오일러의 오각수 정리에서 요구하는 부호 패턴을 구현합니다.
이 알고리즘의 시간 복잡도는 O(n1.5) 수준으로, 단순한 완전 탐색보다 훨씬 효율적으로 큰 n에 대한 분할의 개수를 계산할 수 있다는 장점이 있습니다.