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

문제

풀이

결국 동쪽 다리 M개 중 서쪽 다리 N개를 뽑는 경우의 수 M_C_N이 답일텐데
29! = 8841761993739701954543616000000이라
이 값을 unsigned long long에도 못담는 게 문제였다.
오버플로우가 일어나서 0이나 음수값이 자꾸 출력됐다.

이것보다 큰 자료형이 있나 보니까 __int128을 쓰라는데
MSVC에서는 못쓰고 GCC, Clang 컴파일러에서만 쓴다는데
그게 뭔데 싶고 왜 안풀리고 난린가 싶고
억울하고 속상하고
..

결국 분자 팩토리얼을 계산하면서 분모 팩토리얼을 계산하는 방법으로 해결했다.
뭔가 정수값이니까 이렇게 하면 안될 것 같아서 치워뒀다가
예라이ㅅ 뭐라도 해 봐 하면서 냈는데 이게 되네..

그 외에 자잘하게 넣어준 건

1. M_C_N = M_C_(M-N) 활용해서 계산 시간 줄이기
2. 왼쪽에 다리가 하나일 때 경우의 수는 M개
3. 양쪽 다리 수가 같을 때 경우의 수는 1개

요정도

코드

#include <iostream>
using namespace std;

int t, n, m;

void solution() {
	if (n == 1 || m - n == 1) {
		cout << m << "\n";
		return;
	}
	if (n == m) {
		cout << "1\n";
		return;
	}

	if (n > m - n) n = m - n;

	unsigned long long ans = 1;
	for (int i = 1; i <= n; i++) {
		ans *= m--;
		ans /= i;
	}
	cout << ans << "\n";
	return;
}

int main() {
	cin >> t;
	for (int i = 0; i < t; i++) {
		cin >> n >> m;
		solution();
	}

	return 0;
}

채점

지원자가 최근에 스트레스 받은 경험이 있나요?
실버5를 한 시간 동안 풀었을 때입니다.