C++에서 크기가 N이고 합이 K인 양의 정수 배열의 개수 구하기

두 개의 정수 N과 K가 주어졌을 때, 각 요소가 모두 양의 정수이면서 전체 요소의 합이 K가 되는 크기 N짜리 배열이 총 몇 가지 만들 수 있는지 구하는 문제입니다.

이 문제는 조합론에서 잘 알려진 '별과 막대(Stars and Bars)' 기법으로 해결할 수 있습니다. 크기가 N이고 합이 K인 배열의 개수는 아래 공식 하나로 바로 계산됩니다.

$$\dbinom{k - 1}{n - 1}$$

즉, n개의 양의 정수를 더해서 합이 k가 되는 경우의 수는 C(k−1, n−1), 즉 k−1개 중에서 n−1개를 선택하는 조합과 같습니다. 예시를 통해 확인해 보겠습니다.

예제 1

입력

n = 1
k = 2

출력

1

만들 수 있는 배열은 [2] 하나뿐입니다.

예제 2

입력

n = 2
k = 4

출력

3

만들 수 있는 배열은 [1, 3], [2, 2], [3, 1]로 총 3가지입니다. 공식에 대입해 보면 C(4−1, 2−1) = C(3, 1) = 3으로 결과와 일치합니다.

알고리즘

• 두 수 n과 k를 초기화합니다.
• 숫자의 팩토리얼을 계산하는 함수를 작성합니다.
• 위 공식대로 이항 계수(binomial coefficient)를 계산하는 메인 함수를 작성합니다.
• 결과를 반환합니다.

C++ 구현

다음은 위 알고리즘을 C++로 구현한 코드입니다.

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

int factorial(int n) {
    int result = 1;
    for (int i = 2; i <= n; i++) {
        result *= i;
    }
    return result;
}

int getNumberOfArraysCount(int n, int k) {
    return factorial(n) / (factorial(k) * factorial(n - k));
}

int main() {
    int N = 5, K = 8;
    cout << getNumberOfArraysCount(K - 1, N - 1) << endl;
    return 0;
}

코드에서 getNumberOfArraysCount 함수는 이항 계수 C(n, k)를 계산하며, 실제 호출 시 (K − 1)과 (N − 1)을 인자로 전달해 공식 C(K−1, N−1)을 그대로 적용합니다.

실행 결과

위 코드를 실행하면 다음과 같은 결과를 얻습니다.

35

N = 5, K = 8일 때 합이 8이 되는 5개의 양의 정수 배열은 총 35가지입니다. 이는 C(7, 4) = 35와 일치합니다.

참고 사항

팩토리얼 값은 숫자가 조금만 커져도 매우 빠르게 증가하므로, 위 구현은 N과 K가 작은 경우에 적합합니다. 입력 범위가 크다면 팩토리얼을 직접 계산하는 대신 파스칼 삼각형(DP) 방식으로 이항 계수를 구하거나, 모듈러 연산을 활용해 오버플로우를 방지하는 것이 좋습니다.