11050. 이항 계수 1

백준 11050번 풀이

이 글은 Obsidian에서 마이그레이션되었으며, 그 과정에서 AI의 도움을 받았습니다. 오류나 누락된 내용이 있다면 댓글로 알려주세요!

문제

11050번: 이항 계수 1

풀이

아이디어

이항 계수란 이항식을 이항 정리로 정리했을 때 각 항의 계수이지만, 쉽고 익숙한 표현으로는 _nC_k 이다. 자세한 설명은 위키백과로 대신한다.

이항 계수를 구하는 방법은 정의를 이용한다거나 하는 다양한 방법이 있지만 나는 이항 계수를 구하는 문제가 있을 경우에는 파스칼의 삼각형을 이용한 DP로 푸는 편이다. (파스칼의 삼각형 위키백과)

위의 개념들을 토대로 나는 점화식 _nC_k = _n-1C_k + _n-1C_k-1 을 재귀로 구현해 주었다. 그리고 무작정 재귀를 돌리게 되면 불필요한 반복이 너무 많아지게 되므로 2차원 배열을 할당해 준 뒤에 저장(메모)된 값이 있는 경우에는 계산과정을 거치지 않고 그 값을 바로 반환해 주고, 저장된 값이 없는 경우에만 점화식에 따라서 계산을 해 주었다.

코드

#include <iostream>

using namespace std;

int memo[11][11];
int N, K;

int bi_coef(int n, int k){
    if (k == 0 || n == k)
        memo[n][k] = 1;
    else if (memo[n][k] == 0)
        memo[n][k] = bi_coef(n - 1, k) + bi_coef(n - 1, k - 1);
    return (memo[n][k]);

}

int main(){
    cin >> N >> K;
    cout << bi_coef(N, K);
}