파스칼의 삼각형 조합을 구하는 방법

파스칼의 삼각형으로 조합을 구할 수 있다.

위의 삼각형 형태를 행렬로 바꾸면 하삼각행렬로 만들 수 있다.

(i,j)위치의 값이 정확히 iCj가 되는 예쁜 형태가 된다.

(j==0일때만 1을 넣어주면된다.)

​

ex)[boj]11051_이항계수2

#include <iostream>
#include <algorithm>

using namespace std;

long long pascal[1000][1000];

int main() {
	int N, K;
	int max = 10007;
	cin >> N >> K;

	for (int n = 0; n <= N; n++) {
		for (int k = 0; k <= n; k++) {
			if (k == 0) {
				pascal[n][k] = 1;
			}
			else {
				pascal[n][k] = pascal[n - 1][k] + pascal[n - 1][k - 1];
				if (pascal[n][k] > max) {
					pascal[n][k] = pascal[n][k] % max;
				}
			}
		}
	}

	cout << pascal[N][K] % max << endl;

	return 0;
}

* 중간에 메모리가 터지지 않도록 max으로 나머지계산을 해준다