[11050] 이항 계수 1

[11050] 이항 계수 1

문제

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

입력

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

출력

$\begin{pmatrix}N\\K\end{pmatrix}$를 출력한다.

코드

#include <iostream>

using namespace std;

/* 조건 */
#define MAX_N 10

/* 변수 */
int N, K;
int C[MAX_N+1][MAX_N+1];

/* 함수 */
int combination(int n, int k) {
    if(C[n][k] > 0) return C[n][k];
    if(n == 0) return C[n][k] = 0;
    if(n == k) return C[n][k] = 1;
    if(k == 0) return C[n][k] = 1;
    return C[n][k] = combination(n-1, k-1) + combination(n-1, k);
}

int main() {
    /* 입력 */
    cin >> N >> K;

    /* 풀이 */
    C[0][0] = 1;
    combination(N, K);

    /* 출력 */
    cout << C[N][K];
}

풀이

$_{N}C_{K} = _{N-1}C_{K-1} + _{N-1}C_{K}$ 를 이용해 해결했다.
이 때 시간을 줄이기 위해 메모이제이션으로 배열에 값을 저장하여 해결했다.

이 다음 문제인 [11051] 이항 계수 2 문제도 똑같은 구성으로
MAX_N과 나머지 연산만 해주면 해결된다.

조합에 관한 참조사이트
조합식의 변형
https://j1w2k3.tistory.com/326

출처

백준 [11050] 이항 계수 1
https://www.acmicpc.net/problem/11050