백준 6591 : 이항 쇼다운

www.acmicpc.net/problem/6591

6591번: 이항 쇼다운

n개의 원소에서 k개를 순서 없이 선택하는 방법의 수를 찾는 문제로 문제 자체는 간단하다. 보자마자 조합이 생각날텐데 맨 첨에 정답이 2^31보다 작은 경우만 입력으로 주어진다는 조건을 보지 못해서 무조건 시간초과가 나는데 어떻게 풀어야하나 고민을 좀 했던 문제이다. 

 

정답이 2^31보다 작다면 nCr을 사용해서 쉽게 풀 수 있다. 단, 이 때, nCr = nC(n-r) 이기 때문에 r값이 크게 주어졌을 때 r대신 (n-r)을 사용하면 불필요한 연산을 줄일 수 있다.

#include <iostream>

#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define MIN(a,b) a<b?a:b
using namespace std;

typedef long long ll;

int main() {
	fastio;
	int n, k;
	ll ans = 1;
	while (1) {
		cin >> n >> k;
		if (n + k == 0) break;

		k = MIN(k, n - k);
		for (int i = 0; i < k; i++) {
			ans *= (n - i);
			ans /= (i + 1);
		}
		cout << ans << '\n';
		ans = 1;
	}

	return 0;
}

메모리: 2016 KB

시간: 0 ms

 

ans를 long long으로 선언했는데 정답이 2^31 미만이라고 하니 인트로 풀어도 충분할 것 같다.

 

그리고 추가로 만약 정답이 2^31까지면 절대 안터지나? 싶어서 실제로 가장 많은 연산 횟수가 필요한 경우가 언제고 그 때의 연산 횟수는 얼마일까 궁금해서 아래 코드를 돌려보았다.

 

#include <iostream>

#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define MIN(a,b) a<b?a:b
#define MAX(a,b) a>b?a:b

using namespace std;

typedef long long ll;
int max_cnt = 0;

int main() {
	fastio;
	int k;
	int max_n;
	bool end = 0;
	ll ans = 1;

	for (int n = 1; n < 1e9; n++) {
		if (end) break;
		k = n / 2;
		for (int i = 0; i < k; i++) {
			ans *= (n - i);
			ans /= (i + 1);
			if (ans >= (1 << 31) - 1) { end = 1; break; }
		}
		if (ans < (1 << 31) - 1) {
			if (max_cnt < k) {
				max_cnt = k; max_n = n;
			}
		}
		cout << ans << '\n';
		ans = 1;
	}
	cout << max_n << ' ' << max_cnt;

	return 0;
}

대충 짜서 지저분하다. 사실 정성스럽게 짜도 지저분하다. 쨋든, n과 k를 1부터 21억까지 하나씩 돌리자니 너무 오랜 시간이 걸릴 것 같아 몇가지 조건을 생각해봤다.

 

첫 번째, 연산 횟수는 k에 비례한다. 곱하기 나누기 한 번씩 해서 두 번이지만 그냥 연산 횟수를 k라고 하자.

두 번째, k가 n/2를 넘어가게 되면 k = (n-k)일 때와 중복되므로 k <= n/2 인 범위까지만 생각한다.

세 번째, 연산 횟수는 k에 비례하고 k <= n/2 이므로 n에서 나올 수 있는 k의 최대값은 k = n/2이다.

네 번째, n이 증가함에 따라 nC(n/2)도 증가하므로 ans값이 한 번이라도 2^31을 넘게되면 그 뒤는 볼 필요가 없다.

 

위 조건들에 의해서 nC(n/2)가 2^31 미만인 값들 중 가장 큰 n이 max_n 이 될 것이고 그 때의 k가 연산 횟수가 될 것이다. 이렇게 구해진 max_n 값은 33, k값은 16이었다. 생각보다 연산 횟수가 너무 적어서 허무했다. 이 글을 보시는 분들은 뻘짓하지 마시고 편하게 다음 문제 푸시길 바란다.