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

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

 

 

조합을 통해 풀 수 있는 문제이다. mCn을 통해 다리를 지을 수 있는 경우의 수를 출력해주면 된다.

 

정답코드

#include <iostream>

using namespace std;

int combination(int n, int k) {
	if (k > n - k) k = n - k;  // 계산량을 줄이기 위해 k를 더 작은 값으로 설정
	long long result = 1;
	for (int i = 0; i < k; i++) {
		result *= (n - i);
		result /= (i + 1);
	}
	return result;
}

int main()
{
	int t;

	cin >> t;

	for (int i = 0; i < t; i++)
	{
		int n, m;
		cin >> n >> m;
		cout << combination(m, n) << endl;
	}
}