[백준 1010] 다리놓기 (nCr문제)

조합 문제인데

이 nCr을 n-1Cr-1 + n-1Cr 을 이용해서 dp로 미리 다 구한다음에 답만 출력해주면 됨

 

dp로 미리 모든 nCr을 다 구해놓는 생각을 일단 해야하고

dp의 의의가 뭐냐 memorization 즉 한번 계산한건 다시는 계산하지 않는거임

그래서 n-1Cr-1과 n-1Cr은 이미 계산된 값 즉 dp 2차원 배열 값을 재사용해주면 된다

 

---

#include <iostream>
#define SIZE 30

using namespace std;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	int dp[SIZE][SIZE];

	for (int n = 1; n < 30; n++) dp[n][1] = n;
	for (int n = 1; n < 30; n++) dp[n][n] = 1;

	for (int i = 1; i < 30; i++) {
		for (int k = 2; k < i; k++) {
			dp[i][k] = dp[i - 1][k - 1] + dp[i - 1][k];
		}
	}

	int N; cin >> N;
	int n, r;
	for (int i = 0; i < N; i++) {
		cin >> r >> n;
		cout << dp[n][r] << "\n";
	}

	return 0;
}