백준 6591 이항 쇼다운

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

문제와 채점은 위 사이트에서 확인 하실 수 있습니다

 

이 문제는 nCk를 구하는 문제입니다. 이때 n과 k가 각각 2^31-1 까지 가능하다고 되어 있습니다. 

 

그리고 nCk의 결과값은 항상 2^31보다 작다고 되어 있으므로 아주큰 n과 k를 입력받아도 21억을 못넘으므로 그렇게 연산 횟수가 많지 않을 것이므로 nCk = nPk / k! 을 이용해서 그냥 구해주면 됩니다.

 

이때 주의할 점은 nCk = nCn-k 이므로 만일  1000C998 이 입력된다면 998번 연산을 하는 것이 아니라 1000C2로 바꾸어 생각하여 2번만 연산을 하게 해주어야 시간초과를 피할 수 있습니다. 그리고 답은 int형 범위 안이지만 계산하는 과정에서 그값이 초과 될 수 있으므로 계산하는 변수는 long long으로 선언해주어야 합니다.

 

다음은 코드입니다.

 

#include <iostream>

using namespace std;

int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	int n,k;
	
	while(cin >> n) {
		cin >> k;
		if(n == 0 && k ==0)
			break; 
		long long ans = 1;
		
		
		if(k > n/2)
			k = n-k;
		
		for(int i = 1; i <= k; i++) {
			ans *= n;
			ans /= i;
			n--;
		}
		cout<<ans<<'\n';
		
	}
	return 0;
}