[백준 6591번] 어항 쇼다운 (C++)

문제링크 : https://www.acmicpc.net/problem/6591

6591번: 이항 쇼다운

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

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
   
    int N, K;
    while(1)
    {
        cin >> N >> K;
        if(N==0 && K==0) break;
        ll result = 1;
        int num = min(K, N-K); //K!, (N-K)!
        for(int i=1; i<=num; i++)
        {
            result = result * N/i; //N!/K! or (N-K)!
            N--;
        }
        cout << result << "\n";
    }
    return 0;
}

조합 문제다.

공식은 N! / (K! * (N-K)!)이다.

K!과 (N-K!) 중 큰 값 만큼 N!의 계산과정을 미리 없앨 수 있으므로, 작은 값만큼만 반복하여 나머지 값을 처리한다.