[10942] 팰린드롬?

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

10942번: 팰린드롬?

<문제>

구간에 대해 팰린드롬이 성립하는지에 대한 불리언 값을 출력해야하는 구간쿼리가 M개 들어온다.

일반적인 팰린드롬 판별에 O(N)의 시간복잡도가 소요되므로, 특별한 최적화가 없다면 O(NM)이 걸릴것이다.

문제는, N이 2천, M이 1백만, 0.5초의 시간제한으로 TLE이다.

 

이는 DP를 사용해 최적화가 가능하다. 아래와 같은 사실이 DP최적화의 핵심이다.

1. (S,E)가 팰린드롬이 아니면, (S-1, E+1)도 팰린드롬이 아니다

2. (S,E)가 팰린드롬이고, a[S-1] == a[E+1]이면 (S-1, E+1)은 팰린드롬이다. 

 

<소스코드>

#include<stdio.h>
int n, m, a[2001];
int memo[2001][2001];
int main(void) {
    int i,j,s,e;
    bool res;
    scanf("%d", &n);
    for (i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        memo[i][i] = 1;
        if (i >= 2 && a[i - 1] == a[i])memo[i - 1][i] = 1;
    }
    for (i = 2; i <= n-1; i++) {
        for (j = 1; i + j <= n; j++) {
            if (memo[j + 1][i + j - 1] == 1 && a[j] == a[i+j])memo[j][i+j] = 1;
        }
    }
    scanf("%d", &m);
    while (m--) {
        scanf("%d %d", &s, &e);
        printf("%d\n", memo[s][e]);
    }
    return 0;
}