글 읽기 - 6591번 이항 쇼다운 시간초과...ㅠㅠ

gkfkagkfka12 6년 전 0

조건 1 ) n의 입력값은 최대 INT_MAX

조건 2 ) 결과값도 최대 INT_MAX

따라서 재귀,배열 모두 사용 불가능, 그냥 계산한다. 어쩌피 입력이 저 위의 조건을 만족시켜 들어오니까.

이렇게 풀어봤는데 시간초과가 뜨네요 도와주세요 ㅠㅠ

#include <iostream>

typedef unsigned long long ull;

int main(void)
{
	ull n, m; std::cin >> n >> m;
	ull combination=1, fact = 1;

	while (n || m){
		if (m == 2) combination = (n*(n - 1)) / 2;
		else if (m == 1) combination = n;
		else{
			for (ull i = 2; i <= m; i++) fact *= i;
			for (ull i = n; i >= n - m + 1; i--) combination *= i;
			combination /= fact;
		}
		std::cout << combination << '\n';
		fact = 1, combination = 1;
		std::cin >> n >> m;
	}

	return 0;
}

jseo 6년 전 0

2000000000 2000000000

입력으로 주어지면 시간 초과 걸릴것 같네요. 답은 1 입니다.

jseo 6년 전 0

풀어보진 않았지만 C(n, k) = C(n, n - k) 와 C(n, k) = n * C(n - 1, k - 1) / k를 이용해 풀 수 있을것 같네요.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

6591번 이항 쇼다운 시간초과...ㅠㅠ

gkfkagkfka12 6년 전 0

jseo 6년 전 0

jseo 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말