백준 11050 이항 계수 1 [C++] - 동적 계획법

문제 링크 : https://www.acmicpc.net/problem/11050

11050번: 이항 계수 1

소스코드 

#include <iostream>
using namespace std;
#define MAX 100
int binomial_coefficient(int n, int k) {
	int C[MAX][MAX];
	int m;
	for (int i = 0; i <= n; i++) {
		m = (i < k) ? i : k;
		for (int j = 0; j <= m; j++) {
			if (j == 0 || j == i) C[i][j] = 1;
			else C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
		}
	}
	return C[n][k];
}
int main() {
	int n, k;
	cin >> n >> k;
	cout << binomial_coefficient(n, k);
}

동적 계획법을 사용하여 C[i][j]를 구하려면 배열에서 바로 위에 있는 행의 두 값을 필요로 합니다. 따라서 C[0][0]부터 차례로 행들의 값을 계산해서 내려가면 됩니다. 이 때 k 보다 더 큰 열의 원소들은 C[n][k]를 구하는데 사용될 리가 없기 때문에 계산하지 않습니다.