1010 다리놓기(C++)

1010번: 다리 놓기

구현 문제인척 하는 큰 수 처리 문제

1. 문제

---

간단 설명

N개의 사이트에서 M개의 사이트로 겹치지 않는 다리를 놓는 문제

M개 중 N개를 선택하는 전형적인 조합 문제

2. 문제 분석

---

주의점

1. N, M의 최대값은 30이다

• 조합 공식 nCr = n! / ((n-r)! * r! )을 이용해서 풀 경우, int형으로 30!는 처리가 불가능함

• 30!은 2.6525286e+32로 정수형 최대 큰 자료형인 unsigned long long int 형으로도 처리가 불가능하다 (약1.8e+19 까지 처리 가능)

1. 조합 공식을 조금 수정해서 nCr = (n * n-1 * ... * n-r+1) / (r * r-1 * ... * 2 * 1) 로 풀이

• 30C15 인 경우, 30 * 29 * ... * 15 또한 오버플로우가 남

1. float, double 형 사용

• 부동 소수점은 정수를 다루는 용도로 사용하면 오차가 발생할 수 있으므로 사용하면 안됨!

알고리즘

계산하면서 오버플로우가 발생하지 않도록 처리해줘야한다

1. 테스트케이스 개수 T입력받기
2. N과 M입력 받기
3. N또는 M이 0이라면 불가능하므로 0 출력 후 다음 케이스로 넘어감
4. result 변수에 M부터 M-N+1 까지 차례로 곱해주면서, 1부터 N까지 나눠주는것을 동시에 진행한다
5. 출력 후 2로 돌아간다

필요변수

• 테스트 케이스 개수 int T

• N, M 최대 30

• 결과값 result는 최대한 큰 수를 다룰 수 있도록 unsigned long long int 사용

• nCr 에서 r을 담당할 int r

3. 소스코드

---

#include <iostream>

using namespace std;

int main() {
	// freopen_s(new FILE*, "input.txt", "r", stdin);
	int T, N, M;
	cin >> T;

	while (T--) {
		cin >> N >> M;

		if (N == 0 || M == 0) {
			cout << 0 << endl;
			continue;
		}

		unsigned long long int result = 1;
		int r = 1;

		for (int i = M; i >= M - N + 1; i--) {
			result *= i;
			result /= r;
			r++;
		}
		
		cout << result << endl;
	}

	return 0;
}