글 읽기 - 시간초과가 나오네요... 메모이제이션;;ㅠㅠ

jihyun8386 7년 전 0

답은 제대로 나오는 것 같습니다.

시간초과 문제를 나름 해결해보고자

if(result < 10007) 제어문을 추가해보았지만, 계속 시간초과네요...

어떻게 하면 좋을 까요? 도움 부탁드립니다ㅠㅠ

#include <iostream>
using namespace std;
#define maxx 1000

long long choice(int n, int k) {
	static long long memo[maxx][maxx];
	if (memo[n][k] > 0) return memo[n][k];
	if (k == 0 || n == k)	return memo[n][k] = 1;
	return choice(n - 1, k - 1) + choice(n - 1, k);

}
int main() {

	int n, k;
	long long result;
	cin >> n >> k;
	result=	choice(n, k);
    if(result <10007) cout << result<<endl;
    else cout << result%10007<<endl;
	return 0;
}

cozyyg 7년 전 0

메모이제이션을 하다 말아서 k=0이나 k=n인 경우 말고는 남지를 않습니다.

이러면 그냥 재귀 돌리는 시간이랑 같게 나오겠죠.

그것보다 Binomial(1000,500)은 약 10^299승 정도입니다.

큰 경우에 대한 테스트를 해보세요. 답 같은 거는 wolframalpha 같은 데서 잘 계산해 줄 겁니다.

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

문제

문제

출처

ICPC

시간초과가 나오네요... 메모이제이션;;ㅠㅠ

jihyun8386 7년 전 0

cozyyg 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말