(C++) - 백준(BOJ) 11050번 : 이항계수 1

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

11050번: 이항 계수 1

조합을 구하는 문제였습니다.

 

풀이방법

 1. 이항정리를 이용하는 법 : nCk = n-1Ck +n-1Ck-1

 2. 그냥 구하기

 

Code

 1. 이항정리 이용

#include <bits/stdc++.h>
using namespace std;
int n,k,a[11][11];
//nCk = n-1Ck + n-1Ck-1
int dp(int n, int k){
    if(n == k || k == 0) return 1;
    int &ret = a[n][k];
    if(ret) return ret;
    ret = dp(n-1,k) + dp(n-1,k-1);
    return ret;
}

int main(){
    cin >> n >> k;
    cout << dp(n,k);
}

 

 2. 그냥 구하기

#include <iostream>
using namespace std;
int cnt = 0;
int  Com(int N,int K){
    if (K != cnt){
        cnt++;
        return N*Com(N - 1, K);
    }
    return 1;
}
int Fac(int N, int K) {
    if (K != 0) return (K*Fac(N, K - 1));
    else return 1;
}
int main() {
    int N, K;
    cin >> N >> K;
    cout << Com(N, K) / Fac(N, K);
}