C++에서 nCr(조합) 값 계산하는 프로그램 작성 방법

전체 개수 n과 선택할 개수 r이 주어졌을 때, C는 조합(Combination)을 의미하며, 이 글에서는 nCr의 값을 계산하는 프로그램을 C++로 작성하는 방법을 알아봅니다.

조합은 주어진 집합에서 순서에 상관없이 요소를 선택하는 방법입니다. 순열(Permutation)은 요소를 나열하고 배치하는 과정이라면, 조합은 집합에서 요소를 단순히 선택하는 과정이라는 점에서 서로 다릅니다.

조합을 구하는 공식은 다음과 같습니다.

nCr = (n!) / (r! × (n-r)!)

예제 입력 및 출력

입력: n=12, r=4
출력: 12C4의 값 : 495

알고리즘

시작
1단계 → 팩토리얼을 계산하는 함수 선언
    int cal_n(int n)
    int temp = 1
    int i = 2부터 i <= n까지 반복하며 i++
        temp = temp * i 설정
    반복 종료
    temp 반환
2단계 → nCr을 계산하는 함수 선언
    int nCr(int n, int r)
        return cal_n(n) / (cal_n(r) * cal_n(n - r))
3단계 → main() 함수에서
    변수를 int n = 12, r = 4로 선언
    nCr(n, r) 출력
종료

C++ 전체 코드

#include <bits/stdc++.h>
using namespace std;
// n에 대한 팩토리얼을 계산하는 함수
int cal_n(int n){
    int temp = 1;
    for (int i = 2; i <= n; i++)
        temp = temp * i;
    return temp;
}
// nCr을 계산하는 함수
int nCr(int n, int r){
    return cal_n(n) / (cal_n(r) * cal_n(n - r));
}
int main(){
    int n = 12, r = 4;
    cout << "value of " << n << "c" << r << " is :" << nCr(n, r);
    return 0;
}

실행 결과

value of 12c4 is :495

코드 설명

위 코드는 두 가지 함수로 구성되어 있습니다. 먼저 cal_n() 함수는 2부터 n까지의 값을 곱하여 n! (팩토리얼)을 계산합니다. 그다음 nCr() 함수는 조합 공식인 n! / (r! × (n-r)!)을 그대로 코드로 옮긴 것으로, 세 번의 팩토리얼 계산 결과를 이용해 최종 조합 값을 반환합니다.

main() 함수에서는 n=12, r=4를 대입해 12C4를 계산하며, 결과값 495가 출력됩니다. 즉, 12개 중에서 4개를 선택하는 방법은 총 495가지라는 의미입니다.