이 문제에서는 다음과 같은 형태의 n개 변수를 가진 선형 방정식이 주어집니다.
coeff1(var1) + coeff2(var2) + … + coeffn(varn) = value
목표는 이 선형 방정식을 만족하는 음이 아닌 정수 해의 개수를 구하는 것입니다.
문제 이해를 위한 예시
입력
coeff[] = {3, 5}, value = 8출력
1
설명
방정식 : 3x + 5y = 8
해 : x = 1, y = 1
음이 아닌 정수 범위에서 이 방정식을 만족하는 조합은 (x, y) = (1, 1) 하나뿐이므로 해의 개수는 1이 됩니다.
해결 접근 방법
가장 단순한 풀이 방법은 방정식의 값을 재귀적으로 평가하는 것입니다. 각 계수를 현재 값에서 차감하면서 재귀 호출을 반복하고, 값이 정확히 0이 되면 해당 경로를 하나의 해로 간주하여 카운트를 1 증가시킵니다. 만약 특정 계수가 남은 값보다 크다면 그 계수는 더 이상 사용할 수 없으므로 건너뜁니다. 또한 재귀 호출 시 시작 인덱스를 현재 위치로 전달하여 같은 계수의 중복 조합을 허용하면서도 순서만 다른 중복 해는 세지 않도록 합니다.
구현 예제 코드
#include<iostream>
using namespace std;
int countSolutionsEq(int coeff[], int start, int end, int value) {
if (value == 0)
return 1;
int coefCount = 0;
for (int i = start; i <= end; i++)
if (coeff[i] <= value)
coefCount += countSolutionsEq(coeff, i, end, value -
coeff[i]);
return coefCount;
}
int main() {
int coeff[] = {3, 5, 1, 2};
int value = 6;
int n = sizeof(coeff) / sizeof(coeff[0]);
cout<<"The number of solutions of the linear equation is "<<countSolutionsEq(coeff, 0, n - 1, value);
return 0;
}출력
The number of solutions of the linear equation is 8
위 코드에서 방정식 3a + 5b + c + 2d = 6을 만족하는 음이 아닌 정수 조합은 총 8가지이며, 프로그램은 이를 정확히 계산하여 출력합니다.
복잡도 분석 및 개선 방향
이 재귀 풀이의 시간 복잡도는 입력 값에 따라 지수적으로 증가할 수 있습니다. 탐색 과정에서 동일한 부분 문제가 여러 번 반복해서 등장하기 때문에, 메모이제이션을 활용하거나 동적 계획법(DP)으로 변환하면 중복 계산을 제거하여 성능을 크게 향상시킬 수 있습니다. 따라서 값이 커지는 입력에서는 DP 기반 접근이 더 효율적인 선택입니다.