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

xyzw·2025년 8월 16일

algorithm

목록 보기

64/97

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

풀이 1

이항 계수를 파스칼 삼각형으로 나타냈을 때,
bc[i][j] = bc[i-1][j-1] + bc[i-1][j] 임을 이용하여
DP bottom-up 방식으로 풀었다.

코드 1

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    int N, K;

    cin >> N >> K;
    
    vector<vector<int>> bc(N+1, vector<int>(N+1, 1));
    for(int i=2; i<=N; i++) {
        for(int j=1; j<i; j++) {
            bc[i][j] = bc[i-1][j-1] + bc[i-1][j];
        }
    }

    cout << bc[N][K];

    return 0;
}

풀이 2

풀이 1과 유사하지만, DP top-down 방식으로 풀었다.

코드 2

#include <iostream>
#include <vector>

using namespace std;

vector<vector<int>> bc(11, vector<int>(11));

int dp(int i, int j) {
    if(j == 0 || i == j) return 1;
    if(bc[i][j]) return bc[i][j];
    return bc[i][j] = dp(i-1, j) + dp(i-1, j-1);
}

int main()
{
    int N, K;

    cin >> N >> K;

    cout << dp(N, K);

    return 0;
}

풀이 3

이항 계수는 nCk = n! / (k!(n-k)!) 이므로
이 계산식을 그대로 구현하였다.

코드 3

#include <iostream>

using namespace std;

int factorial(int num) {
    int mul = 1;
    for(int i=1; i<=num; i++) mul *= i;
    return mul;
}

int main()
{
    int N, K;

    cin >> N >> K;

    if(K == 0 || N == K) cout << 1;
    else cout << factorial(N) / (factorial(K) * factorial(N-K));

    return 0;
}