[BOJ] 11050. 이항 계수 1

백준 온라인 저지에 있는 11050번 이항 계수 1 문제 풀이입니다. 

 

주어지는 자연수 N과 K에 대한 이항 계수를 구하는 문제입니다.

이항 계수란 N개의 수 중에서 K개를 고르는 경우의 수로 아래와 같이 구하면 되는데요.

딱 보고 떠오르는 생각은 각각의 팩토리얼을 구해서 계산하면 되겠네~ 였습니다.

여기서❗️ 줄일 수 있는 중복되는 부분이 있는데요.

팩토리얼이 1부터 N까지를 차례대로 곱한 수이잖아요.

그리고 n-k와 k는 둘다 N보다 작을 것이구요.

그럼 둘중에 하나는 계산을 생략하고 n!에 바로 나눠줬다고 생각하면 중복되는 부분이 줄어들겠더라구요.

글로 이해가 잘 안가실수도 있어서 예제에 있는 숫자로 예를 들어보면

 

N=5, K=2의 이항계수는
5*4*3*2*1 / (3*2*1)*(2*1) 이런식이 됩니다.
5*4*3*2*1 / (3*2*1)*(2*1)
여기서 중복되는 빨간 부분을 처음부터 나눠주고 생각해버리는거죠!
그럼 5*4 / 2*1 이만큼만 계산하면 되기 때문에 팩토리얼을 구하는 과정이 훨씬 짧아집니다.

그래서 아래와 같이 짜봤습니다. 😊

 

#include <iostream>

using namespace std;

int n, k;
int denominator = 1;
int numberator = 1;

int main() {
    cin.tie(0); cout.tie(0);
    ios::sync_with_stdio(0);
    
    cin >> n >> k;
    
    for(int i=max(n-k, k)+1; i<=n; i++) {
        numberator *= i;
    }
    for(int i=2; i<=min(n-k, k); i++) {
        denominator *= i;
    }
    
    cout << numberator/denominator;
    
    return 0;
}

 

https://www.acmicpc.net/problem/11050

 

11050번: 이항 계수 1