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

가장 기초적인 조합 문제 입니다.

이전에는 재귀 함수로 조합 공식의 팩토리얼을 구하는 방법으로 풀었었는데

해당 점화식을 이용해 문제를 해결해보겠습니다.

$i$개 중에 $j$개를 뽑는 조합의 점화식은 다음과 같습니다.

$D[i][j] = D[i-1][j-1] + D[i-1][j]$

먼저 DP 테이블을 다음과 같이 초기화 합니다.

1. $D[i][1]=i$, $i$개 중에 1개를 뽑는 경우의 수는 $i$개
2. $D[i][0]=1$, $i$개 중에 1개도 뽑지 않는 경우의 수는 1
3. $D[i][i]=1$, $i$개 중에 $i$개를 뽑는 경우의 수는 1

#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <stack>
#include <deque>
#include <queue>
#include <string>
#include <climits>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>

using namespace std;

using int32 = long;
using int64 = long long;


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

    int N, K;
    cin >> N >> K;

    int DP[11][11] = {{0}};

	// DP 초기화
    for(int i=1; i<=N; i++)
    {
        DP[i][1] = i;
        DP[i][0] = 1;
        DP[i][i] = 1;
    }

	for(int i=2; i<=N; i++)
	{
		for(int j=1; j<=K; j++)
		{
            DP[i][j] = DP[i - 1][j - 1] + DP[i - 1][j];
		}
	}

    cout << DP[N][K];
    
    return 0;
}