[DP] 백준-다리놓기 C++ 1010번

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

1010번: 다리 놓기

#include <iostream>
using namespace std;

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

	int T;
	cin >> T;
	long long sum = 1;
	int n, m;
	for (int i = 0; i < T; i++)
	{
		cin >> n >> m;

		sum = 1;
		for (int j = 1; j <= n; j++)
		{
			sum = sum * m-- / j;
		}

		cout << sum << '\n';
	}

	return 0;
}

#include <iostream>  
using namespace std;

int dp[31][31];

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

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

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

	int t;
	cin >> t;
	while (t--)
	{
		int n, m;
		cin >> n >> m;
		cout << dp[n][m] << '\n';
	}

	return 0;
}

조합(Combination): 

서로 다른 n개에서 순서를 생각하지 않고 r개를 택하는 것을 n개에서 r개를 택하는 조합이라고 한다. 조합의 관점은 순서가 달라도 내용물이 동일하면 하나로 취급한다. 즉, 조합의 관점에서 다음 두 배열은 같다. ({A,B,C}, {C,A,B})

그래서 같은 조건이라면 순열의 경우의 수가 조합의 경우의 수보다 많다.