글 읽기 - 왜 시간초과가나는지 지적부탁드립니다 고수분들 ㅜ.

isvara 4년 전 0

우선 미리 전처리를 통해서 left,right모든 구간을 다구하면

2000*2000=4백만의 경우의 수를 다구합니다.

그다음 M으로나오는 백만의 case를 다조사한다면 어차피 상수시간이니

5백만정도의 시간복잡도를 예상을 했는데

시간초과가 걸려버립니다.

반복적dp로 풀어야 시간 초과가 안날까요?

어떤 부분에서 제 코드가 시간초과가 나는지 답변부탁드립니다.

#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;

int N,M;
int sequence[2001];
int cache[2001][2001];

int isPalindrome(int left,int right)
{
	int &ref = cache[left][right];
	if (ref != -1)
		return ref;
	
	ref = 1;

	if (left == right)
		return ref;
	
	if (sequence[left] != sequence[right])
		return ref = 0;

	if (left + 1 < right)
	{
		if (!isPalindrome(left + 1, right - 1) == 1)
			return ref = 0;
	}

	return ref;
}
int main()
{
	memset(cache, -1, sizeof(cache));

	scanf("%d", &N);
	for (int i = 1; i <= N; i++)
	{
		int tmp;
		scanf("%d", &tmp);
		sequence[i] = tmp;
	}

	for (int left = 1; left <= N; left++)
		for (int right = left; right <= N; right++)
			isPalindrome(left, right);
	
	scanf("%d", &M);
	while (M--)
	{
		int s, e;
		cin >> s >> e;
		cout << cache[s][e] << endl;
	}
	return 0;
}