백준 10942 팰린드롬?

https://www.acmicpc.net/problem/10942

10942번: 팰린드롬?

팰린드롬이란 예전 광고에서 나온 앞뒤가 똑같은 전화번호를 생각하면된다. 즉 앞으로 읽어도 뒤로 읽어도 똑같은 것을 찾으면된다.

 

재귀로 하나하나 비교하면서 start, end 값이 같으면 1을 반환 다르면 0을 반환한다고 치면 가볍게 문제를 해결할 수 있다고 생각하지만 이 문제는 0.5초가 제한 시간이기 때문에 시간 초과가 발생한다. 

 

그래서 위 문제를 해결하기 위해서는 반복을 하는 동안 중간중간에 기록을 하는 것이다. [1][2]는 1번째 숫자와 2번째 숫자가 팰린드롬인가??

[2][6]는 팰린 드롬인가? 

 

[2][6]이면 재귀에 따라 들어가면 [3][5]도 측정하고 [4][4]를 측정하게 되어 모두 기록하고 기록해 놓은 곳에 방문한다면 탐색하지 않고 그 값을 출력합니다. 

#include <cstdio>
#include <string.h>

int N, S, E, M;
int dp[2002][2002];
int data[2002];

void input();
int isPalin(int start, int end);

int main(){
	memset(dp, -1, sizeof(dp));
	input();
}

void input(){
	scanf("%d", &N);
	for(int i = 1; i <= N; i++)
		scanf("%d", &data[i]);
	scanf("%d", &M);
	for(int i = 1;i <= M; i++){
		scanf("%d %d", &S, &E);
		printf("%d\n", isPalin(S, E));
	}
}


int isPalin(int start, int end){
	if(dp[start][end] != -1){
		return dp[start][end];
	}

	if(start > end)
		return 1;
	else if(data[start] != data[end]){
		dp[start][end] = 0;
		return 0;
	}else{
		dp[start][end] = isPalin(start+1, end-1);
		return dp[start][end];
	}
}