[BOJ-11050][C++] 이항 계수 1

문제

자연수 `N`과 정수 `K`가 주어졌을 때 이항 계수 ${N \choose K}$를 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 `N`과 `K`가 주어진다. ($1 ≤ N ≤ 10, 0 ≤ K ≤ N$)

 

출력

${N \choose K}$ 를 출력한다.

 

예제 입력 1

5 2

 

예제 출력 1 

10

 

알고리즘 분류

• 수학
• 구현
• 조합론

 

문제 출처

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

11050번: 이항 계수 1

 

---

 

문제 해결 방법

• 이항 계수를 구하는 알고리즘을 이용하여 문제를 해결하였다. 
  • 관련 게시글 : https://dev-astra.tistory.com/276

int nCk(int n, int k) {
    if (k > n) {
        return 0;
    }
    if (k == 0 || k == n) {
        return 1;
    }
    return nCk(n - 1, k - 1) + nCk(n - 1, k);
}

 

• 혹은 다음과 같이 메모이제이션(Memoization)을 이용하여 문제를 풀 수 있다.

int dp[11][11];

int nCk(int n, int k) {
    if (dp[n][k] > 0) return dp[n][k];
    else if (k == 0 || k == n) return dp[n][k] = 1;
    else if ((0 < k) && (k < n)) return dp[n][k] = nCk(n - 1, k - 1) + nCk(n - 1, k);
    else return 0;
}

 

코드

#include <iostream>
using namespace std;

int N, K;

int nCk(int n, int k) {
    if (k > n) {
        return 0;
    }
    if (k == 0 || k == n) {
        return 1;
    }
    return nCk(n - 1, k - 1) + nCk(n - 1, k);
}

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

    cin >> N >> K;

    cout << nCk(N, K) << '\n';

    return 0;
}

 

채점 결과

 

참고

• [단계별로 풀어보기] > [정수론 및 조합론]
• 브론즈I