방정식 x1 + x2 + … + xn = k의 정수 해의 개수를 구하는 문제는 조합론의 별과 막대(stars and bars) 기법으로 간단하게 해결할 수 있습니다.
핵심 공식
- 음이 아닌 정수 해(변숫값이 0 이상인 경우)의 개수는 C(n+k−1, k) 입니다.
- 양의 정수 해(변숫값이 1 이상인 경우)의 개수는 C(k−1, n−1) 입니다.
문제에서 제한 조건 없이 모든 정수 해를 요구한다면, 위 두 가지 경우의 수를 더하면 됩니다.
예제
입력
n = 4
k = 7
출력
140
n = 4, k = 7일 때 음이 아닌 정수 해의 개수는 C(10, 7) = 120이고, 양의 정수 해의 개수는 C(6, 3) = 20입니다. 따라서 전체 해의 개수는 120 + 20 = 140이 됩니다.
알고리즘
- n과 k를 초기화합니다.
- 조합 공식을 이용해 음이 아닌 정수 해의 개수 C(n+k−1, k)와 양의 정수 해의 개수 C(k−1, n−1)를 각각 계산합니다.
- 두 값을 더합니다.
- 결과를 출력하고 종료합니다.
C++ 구현
다음은 위 알고리즘을 C++로 구현한 코드입니다.
#include <bits/stdc++.h>
using namespace std;
// 팩토리얼 계산
int factorial(int n) {
int product = 1;
for (int i = 2; i <= n; i++) {
product *= i;
}
return product;
}
// 조합 nCr 계산
int nCr(int n, int r) {
return factorial(n) / (factorial(n - r) * factorial(r));
}
int main() {
int n = 4;
int k = 7;
cout << nCr(n + k - 1, k) + nCr(k - 1, n - 1) << endl;
return 0;
}
실행 결과
위 코드를 실행하면 다음과 같은 결과가 출력됩니다.
140
참고 사항
팩토리얼 방식은 n이 커질 경우 int 범위를 초과해 오버플로우가 발생할 수 있습니다. 실전 문제에서는 큰 수 연산이 필요하다면 long long 타입을 사용하거나, 곱셈과 나눗셈을 교차하여 계산하거나 모듈러 연산을 적용하는 것이 안전합니다.