10942번: 팰린드롬?

코드

시간 : 312 ms

메모리 : 17728 KB

#include<bits/stdc++.h>
using namespace std;

int dp[2005][2005];
int arr[2005];

int main(){
    int n,M;
    memset(arr,-1,sizeof(arr));
    memset(dp,0,sizeof(dp));
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%d",&arr[i]);
    }
    scanf("%d",&M);

    for(int i=0;i<n/2;i++){
        dp[i][i] = 1;
        if(arr[i] == arr[i+1]){
            dp[i][i+1] = 1;
        }
        
        for(int j=0;j<=i;j++){
            if(arr[i-j] == arr[i+j] && dp[i-j+1][i+j-1] == 1){
                dp[i-j][i+j] = 1;
            }
            if(arr[i-j] == arr[i+j+1] && dp[i-j+1][i+j] == 1){
                dp[i-j][i+j+1] = 1;
            }
        }
    }

    for(int i=n/2;i<n;i++){
        dp[i][i] = 1;
        if(arr[i] == arr[i+1]){
            dp[i][i+1] = 1;
        }
        
        for(int j=0;j<=n-i;j++){
            if(arr[i-j] == arr[i+j] && dp[i-j+1][i+j-1] == 1){
                dp[i-j][i+j] = 1;
            }
            if(arr[i-j] == arr[i+j+1] && dp[i-j+1][i+j] == 1){
                dp[i-j][i+j+1] = 1;
            }
        }
    }

    for(int q=0;q<M;q++){
        int s,e;
        scanf("%d %d",&s,&e);
        printf("%d\\n",dp[s-1][e-1]);
    }
}