10942 팰린드롬?

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

10942번: 팰린드롬?

 

d[i][j] = 구간 [i,j]가 팰린드롬인지 여부

 

팰린드롬의 성질을 이용해서 구간을 확장시켜가면서 a[i]와 a[j]가 같을 때, d[i+1][j-1]이 참인지 확인하면 된다.

 

#include <cstdio>
 
int i,j,k,n,m,p,q,a[2001];
bool d[2001][2001];
 
int main()
{
    scanf("%d",&n);
    for(i=1;i<=n;i++)
    {
        scanf("%d",&a[i]),d[i][i]=1;
        if(a[i-1]==a[i]) d[i-1][i]=1;
    }
    for(k=3;k<=n;k++) for(i=1,j=k;j<=n;i++,j++)
        if(a[i]==a[j] && d[i+1][j-1]) d[i][j]=1;
    scanf("%d",&m);
    while(m--) scanf("%d %d",&p,&q),printf("%d\n",d[p][q]);
    return 0;
}