글 읽기 - 메모이제이션을 해도 시간초과발생합니다.

jumpingz 6년 전 0

top-down 으로 해결은 했는데 이를 bottom-up 방식으로도 해결해보려고 노력중인데요..

자꾸 시간초과가 발생하네요.

조건을 잘못처리해서인건지 아니면 애초에 재귀연산이 너무많아서 그런건지 알려주세용 ㅠ

#include <cstdio>
#define INF 1000000007
#pragma  warning(disable:4996)
long long int D[101][101][101];

long long int Build(long long int N, long long int L, long long int R);

int main()
{
	long long int N, L, R;
	scanf("%lld%lld%lld", &N, &L, &R);
	printf("%lld",Build(N, L, R));

	return 0;
}

long long int Build(long long int N, long long int L, long long int R)
{
	if (N <= 0)
		return 0;

	if (D[N][L][R] != 0)
		return D[N][L][R] % INF;

	if (N == 1 && L == 1 && R == 1)
		return D[N][L][R] = 1;

	D[N][L][R] = Build(N - 1, L, R) * (N - 2) % INF;

	if (L > 1)
	{
		D[N][L][R] += Build(N - 1, L - 1, R);
		D[N][L][R] %= INF;
	}
		
	if (R > 1)
	{
		D[N][L][R] += Build(N - 1, L, R - 1);
		D[N][L][R] %= INF;
	}
		
	return D[N][L][R];
}

cprayer 6년 전 0

D[N][L][R]의 연산 결과가 0인 경우에 중복적으로 계산되는 경우가 발생합니다. D 배열을 -1로 초기화하시고 하시면 될 듯 합니다.

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

문제

문제

출처

ICPC

메모이제이션을 해도 시간초과발생합니다.

jumpingz 6년 전 0

cprayer 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말