[백준]1010_다리 놓기

https://www.acmicpc.net/problem/1010

Solved

✔ 알고리즘 분류: DP, 조합론
✔ 안겹치도록 다리를 짓자!
✔ way1. 어차피 n개와 m개의 점이 있다면 m 개의 점은 mCn만큼 골라야 한다. =>Combination
✔ way2. 감이 잘 안올땐 뭐다? 점화식.
dp[n][m] = n개와 m개의 점 사이의 다리를 만들 수 있는 경우의 수일 때,
dp[1][1] = 1, dp[1][2] = 2, dp[1][x] = x 이다.
dp[2][4]의 경우 오른쪽 점 4개 중 가장 위의 점으로 갈 때는 경우의 수가 dp[1][3]과 같고,
오른쪽 점 4개 중 두 번째로 높은 점으로 갈 때는 경우의 수가 dp[1][2]과 같다.
오른쪽 점 4개 중 세 번째로 높은 점으로 갈 때는 경우의 수가 dp[1][1]과 같으니
dp[2][4] = dp[1][3] + dp[1][2] + dp[1][1] 이 된다.
이렇게 식을 계속해서 이어가다 보면
dp[x][y] = dp[x-1][y-1] + dp[x-1][y-2] + ... + dp[x-1][x-1] 라는 점화식이 세워진다.

using namespace std;
#include <iostream>

int dp[31][31];

// mCn
int comb(int m, int n) {
	if (m == n || n == 0)
		return 1;
	if (dp[m][n]) return dp[m][n];

	return dp[m][n] = comb(m - 1, n - 1) + comb(m - 1, n);
}
int main() {
	int n, m;
	int t;

	cin >> t;
	while (t--) {
		cin >> n >> m;
		cout << comb(m,n) << '\n';
	}
};