이번 튜토리얼에서는 합 방정식(sum equation)의 음이 아닌 정수(non-negative integer) 해가 총 몇 개인지 구하는 프로그램을 C++로 작성해 보겠습니다.
문제에서 다루는 방정식은 다음과 같습니다.
x + y + z = n
자연수 n이 주어졌을 때, 이 방정식을 만족하는 음이 아닌 정수(x, y, z ≥ 0) 조합이 몇 가지 존재하는지 찾아야 합니다. 예제를 통해 살펴보겠습니다.
입력 및 출력 예시
입력
2
출력
6
n = 2일 때 가능한 해는 다음 6가지입니다.
0 0 2
0 1 1
0 2 0
1 0 1
1 1 0
2 0 0
알고리즘
가장 직관적인 방법은 세 변수의 모든 조합을 탐색하는 것입니다. 단계별로 정리하면 다음과 같습니다.
- 숫자 n을 초기화합니다.
- 해의 개수를 저장할 count 변수를 0으로 초기화합니다.
- 세 개의 중첩 반복문을 사용해 세 숫자의 모든 조합을 확인합니다.
- 각 조합이 방정식 x + y + z = n을 만족하는지 검사합니다.
- 조건을 만족하면 count를 1 증가시킵니다.
- 탐색이 끝나면 count를 반환합니다.
C++ 구현
위 알고리즘을 C++로 구현한 코드는 다음과 같습니다.
#include <bits/stdc++.h>
using namespace std;
int getEquationSolutionCount(int n) {
int count = 0;
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= n - i; j++) {
for (int k = 0; k <= n - i - j; k++) {
if (i + j + k == n) {
count++;
}
}
}
}
return count;
}
int main() {
int n = 10;
cout << getEquationSolutionCount(n) << endl;
return 0;
}
실행 결과
위 코드를 실행하면 다음과 같은 결과가 출력됩니다.
66
n = 10일 때 방정식 x + y + z = 10을 만족하는 음이 아닌 정수 해는 총 66개입니다.
시간 복잡도 분석
세 개의 중첩 반복문을 사용하기 때문에 시간 복잡도는 O(n³)입니다. 하지만 코드에서 각 반복문의 범위를 n - i, n - i - j로 제한했기 때문에 실제 연산 횟수는 전체 O(n³)보다 적습니다.
참고로, 이 문제는 수학적으로 중복 조합 공식을 이용해 O(1)에도 계산할 수 있습니다. 음이 아닌 정수 해의 개수는 C(n+2, 2) = (n+1)(n+2)/2와 같습니다. 예를 들어 n = 10이면 (11 × 12) / 2 = 66으로, 위 코드의 실행 결과와 일치합니다. n이 매우 큰 경우에는 이 공식을 활용하는 것이 효율적입니다.