[C++]백준11050 이항 계수 1

03 Dec 2022 in Study on Algorithm

백준11050 이항 계수 1 링크

문제

예제 입력

---

코드

#include<iostream>
#include<algorithm>
using namespace std;

int Factorial(int num) {
    //재귀 이용.
    //if (num == 1 || num == 0) {
    //    return 1;
    //}
    //else {
    //    return Factorial(num - 1) * num;
    //}

    //반복문 이용.
    if (num == 0) return 1;

    int result = 1;

    for (int i = num; i >= 1; i--) {
        result *= i;
    }

    return result;

}

int main() {
    cin.sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int  n, k;
    cin >> n >> k;
 
    cout << Factorial(n) / (Factorial(k) * Factorial(n - k));
}

설명

기본적으로 C/C++의 기본 입출력함수를 혼합하여 사용되게 만들었지만 그만큼 실행속도에서 차이가 생기기 때문에 설정을 해주며 입력을 받고 이항 계수는 이항정리에서 전개된 항의 계수를 의미로 조합으로도 나타냅니다. 그 조합을 팩토리얼(Factorial)을 사용해서 N!/K!(N-K)!로 계산할 수 있습니다. 또한, 팩토리얼을 구현하는데 재귀함수나 반복문을 사용할 수 있는데 속도를 생각하여 반목문으로 구현했습니다.
처음에는 algorithm헤더에 있는 순열(prev_permutation or next_permutation)을 사용하여 조합을 구현했습니다.

    int idx[10], cnt = 0;
    for (int i = 0; i < n; i++) {
        if (i < k)
            idx[i] = 1;
        else
            idx[i] = 0;
    }
    do {
        cnt++;
    } while (prev_permutation(idx, idx + n));

    cout << cnt;

---

결과