180124_10942_팰린드롬?

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

#include <iostream>

#include <stdio.h>

using namespace std;

int num[2001];

bool dp[2001][2001];

int main()

{

int n, m;

int start, end;

scanf("%d",&n);

for(int i=1; i<=n; i++) scanf("%d",&num[i]);

scanf("%d",&m);

for(int i=1; i<=n; i++)

{

dp[i][i]=1;

if(i!=n && num[i]==num[i+1]) dp[i][i+1]=1;

}

for(int i=2; i<=n; i++) // i start->end까지의 길이

{

for(int j=1 ; j<=n-i; j++)

{

if(dp[j+1][j+i-1] && num[j]==num[j+i])

{ dp[j][j+i]=1;}

}

}

for(int i=0; i<m; i++)

{

scanf("%d %d",&start,&end);

printf("%d\n",dp[start][end]);

}

}

*주의 

dp[1][1]부터해서 행 순으로 구하면 제대로 안 구해짐

(dp[1][2],dp[1][3],dp[1][4],dp[1][5],...)

dp[1][5]를 구하기 위해서는 dp[2][4]을 먼저 구해야함

따라서 팰린드롬의 길이 순으로 구함

길이가 2인 dp값부터 구하면

dp[1][3], dp[2][4], dp[3][5], dp[4][6], ...

dp[1][4], dp[2][5], dp[3][6], dp[4][7],...

순으로 더 작은 단위부터 구할 수 있음

또 cin, cout을 사용하면 시간 초과 걸림