C++에서 a = c, b = d 조건을 만족하도록 숫자를 네 부분으로 나누는 경우의 수 구하기

문제 소개

자연수 n이 주어졌을 때, 이 수를 네 부분 (a, b, c, d)으로 나누되 a = c이면서 b = d를 만족하는 분할 방법이 몇 가지 있는지 구하는 문제입니다.

예를 들어 n = 20이라면 정답은 4가 됩니다. 실제로 가능한 조합은 다음과 같습니다.

• [1, 1, 9, 9]
• [2, 2, 8, 8]
• [3, 3, 7, 7]
• [4, 4, 6, 6]

접근 방식

네 부분의 합이 n이 되어야 하고 a = c, b = d이므로 식을 정리하면 다음과 같습니다.

a + b + c + d = n → 2a + 2b = n → a + b = n / 2

이 관계를 이용하면 반복문 없이도 아래와 같은 규칙만으로 답을 바로 계산할 수 있습니다.

• n이 홀수인 경우: 두 값의 합이 정수 n/2가 될 수 없으므로 답은 항상 0입니다.
• n이 4의 배수인 경우: 답은 n/4 − 1입니다. 네 부분이 모두 같은 값이 되는 경우(예: n = 20일 때 [5, 5, 5, 5])는 별도의 방법으로 세지 않기 때문입니다.
• 그 외의 짝수인 경우: 답은 n/4(정수 나눗셈 결과)입니다.

이 풀이법은 간단한 조건 검사만으로 해를 구하므로 시간 복잡도가 O(1)이라는 큰 장점이 있습니다.

C++ 구현 예제

#include <iostream>
using namespace std;

int countPossiblity(int num) {
    if (num % 2 == 1)
        return 0;
    else if (num % 4 == 0)
        return num / 4 - 1;
    else
        return num / 4;
}

int main() {
    int n = 20;
    cout << "Number of possibilities: " << countPossiblity(n);
}

실행 결과

Number of possibilities: 4

마무리

이 문제는 수학적 성질을 먼저 파악하면 어렵지 않게 해결할 수 있습니다. 핵심은 a + b = n/2라는 관계를 찾아내고, n의 홀짝성과 4의 배수 여부에 따라 경우를 나누어 처리하는 것입니다. 완전 탐색 없이 상수 시간에 답을 구할 수 있으므로 입력 값이 매우 커지더라도 안정적으로 동작합니다.