문제

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

풀이

Aha! (핵심)

• 조합 이용
  • M개 중에 N개를 '순서 상관없이' 뽑는 경우의 수
  • 다리끼리 겹칠 수 없다. --> 순서 상관없이 일단 동쪽 점 N개를 고른다. 그러면 어차피 순서는 자동으로 결정되니까.
    (서쪽: 위에서 n번째 점, 동쪽: 고른 것 중 위에서 n번째 점) 이렇게.

어려웠던 점

• N이 너무 클 때는 연산 과정에서 너무 큰 수가 나온다. long long으로 커버 불가.
  --> 이런 자료형 문제는 실행할 때 오류가 뜨는 것도 아니고, 예시는 잘 출력되는데 제출하면 틀렸습니다 가 나와서 원인을 찾는 게 어려웠다.

코드

#include <iostream>

using namespace std;

int main() {
	int T; cin >> T;

	while (T--) {
		int N, M; cin >> N >> M;
		long long result = 1; //다리 개수 = 조합 mCn

		/*조합 계산하기*/
		if (N > M / 2) //N이 너무 클 때는 long long으로 커버 불가
			N = M - N; //mCm-n로 바꿔서 계산
		for (int i = M; i > M - N; i--)
			result *= i;
		for (int i = 1; i <= N; i++)
			result /= i;
		cout << result << "\n";
	}

	return 0;
}