C++로 방정식 x + y + z ≤ n의 해의 개수 구하기

이 글에서는 방정식 x + y + z ≤ n을 만족하는 해가 총 몇 가지인지 구하는 방법을 다룹니다. 문제에서 x, y, z는 각각 정해진 최댓값 X, Y, Z 이하의 음이 아닌 정수여야 하며, 세 변수의 합이 n 이하가 되는 모든 조합의 개수를 세는 것이 목표입니다. 먼저 간단한 예제를 통해 문제를 확인해 보겠습니다.

입력: X = 1, Y = 1, Z = 1, n = 1

출력: 4

입력: X = 1, Y = 2, Z = 3, n = 4

출력: 20

첫 번째 예제에서 조건을 만족하는 해는 (0, 0, 0), (1, 0, 0), (0, 1, 0), (0, 0, 1)의 네 가지입니다. 두 번째 예제 역시 아래에서 소개할 코드를 실행하면 정확히 20가지를 얻을 수 있습니다.

문제 해결 접근 방법

가장 기본이 되는 방법은 브루트 포스(Brute Force), 즉 가능한 모든 조합을 하나씩 검사하는 완전 탐색입니다. 단순하게 구현하면 x, y, z에 대해 세 겹의 반복문이 필요해 O(X × Y × Z)의 시간이 걸리지만, 간단한 관찰 하나로 반복문 하나를 제거하여 O(X × Y)까지 줄일 수 있습니다.

핵심 아이디어: z의 범위는 자동으로 정해진다

x와 y의 값을 먼저 고정하면 z가 가질 수 있는 값의 범위가 자동으로 결정됩니다. z가 만족해야 할 조건을 정리하면 다음과 같습니다.

변수 자체의 제한: 0 ≤ z ≤ Z
방정식의 제한: x + y + z ≤ n 에서 유도되는 z ≤ n − x − y

따라서 z는 0부터 min(Z, n − x − y)까지의 값을 가질 수 있으며, 가능한 값의 개수는 min(Z, n − x − y) + 1개입니다. 만약 n − x − y가 음수가 되면 어떤 z를 골라도 조건을 만족할 수 없으므로 해당 경우는 건너뛰면 됩니다.

C++ 구현 예제

#include<bits/stdc++.h>
using namespace std;

int main(){
    int X = 1, Y = 2, Z = 3, n = 4; // x, y, z의 최댓값과 주어진 n
    int answer = 0; // 해의 개수를 세는 카운터

    for(int x = 0; x <= X; x++){
        for(int y = 0; y <= Y; y++){
            int remain = n - x - y; // z에 배분할 수 있는 남은 값
            if(remain < 0) break;   // 더 이상 조건을 만족하는 z가 없음
            // z는 0 이상 min(Z, remain) 이하의 값을 가질 수 있다
            answer += min(Z, remain) + 1;
        }
    }
    cout << answer << "\n";
}

실행 결과

코드 설명

바깥쪽 반복문으로 x를, 안쪽 반복문으로 y를 하나씩 고정합니다. 이후 n − x − y를 계산해 z에 사용할 수 있는 '남은 양'을 구하고, 그 값이 음수라면 더 큰 y에서도 조건을 만족할 수 없으므로 내부 반복을 종료(break)합니다. 그렇지 않다면 z의 후보 개수인 min(Z, remain) + 1을 정답에 누적합니다. 이 과정을 모든 (x, y) 조합에 대해 반복하면 전체 해의 개수를 구할 수 있습니다.

예를 들어 x = 0, y = 0일 때 remain은 4이므로 z는 0부터 3까지 네 가지 값을 가질 수 있고, x = 1, y = 2일 때 remain은 1이므로 z는 0 또는 1의 두 가지만 가능합니다. 이처럼 각 조합의 경우의 수를 모두 더하면 답인 20이 도출됩니다.

시간 및 공간 복잡도

시간 복잡도: O(X × Y) — 두 겹의 반복문이 전체를 지배하며, 내부 연산은 상수 시간에 수행됩니다.
공간 복잡도: O(1) — 카운터 변수 외에 추가적인 메모리가 필요하지 않습니다.

참고: 변수에 상한이 없다면?

x, y, z에 개별 상한이 없고 음이 아닌 정수라는 조건만 있다면 반복문 없이도 해의 개수를 바로 계산할 수 있습니다. 중복조합 공식에 따르면 x + y + z ≤ n의 해의 개수는 C(n + 3, 3) = (n + 1)(n + 2)(n + 3) / 6입니다. 예를 들어 n = 1일 때 C(4, 3) = 4로, 첫 번째 예제의 결과와 일치합니다.

마무리

이 글에서는 방정식 x + y + z ≤ n을 만족하는 해의 개수를 브루트 포스 기반의 최적화된 탐색으로 구하는 방법을 살펴보았습니다. 핵심은 두 변수를 고정했을 때 마지막 변수의 범위가 수학적으로 바로 결정된다는 점이며, 이를 활용하면 O(X × Y) 시간 복잡도로 문제를 해결할 수 있습니다. 동일한 로직은 C, Java, Python 등 다른 프로그래밍 언어로도 손쉽게 옮겨 작성할 수 있습니다.