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

 

문제 1010번

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

 

n에서 순서상관없이 m개를 선택하는 것이기 때문에 nCm을 사용한다.

nCm에서 n이 5이고 m이 2라면 (5x4)/(2x1)이다. 따라서 m-n+1부터 m까지 곱(예시 5x4)해주고, 여기에 j - (m - n)을 나눠준다. 그러면 1부터 시작하여 해당 수까지 나눌 수 있다.

#include <iostream>
using namespace std;

int main() {
	int T, n, m;
	cin >> T;

	for (int i = 0; i < T; i++) {
		int result = 1;
		cin >> n >> m;
		
		for (int j = m - n + 1; j <= m; j++) {
			result *= j;
			result /= j - (m - n);
		}
		cout << result << '\n';
	}
	
	return 0;
}