백준 10942 / 팰린드롬?

거꾸로 읽어도 같은 것을 팰린드롬이라고 한다.

처음엔 스트링으로 받은다음 reverse를 사용하여 풀어보려 했는데 시간초과. O(MN)인데

M의 최대가 백만이니 시간초과가 날수 밖에.

그리하여 다이나믹 프로그래밍으로 풀었다.

D[S][E]를 S번째 수부터 E번째 수까지 팰린드롬이면 1 아니면 0 아직 구하지 못했으면 -1로 설정했다.

탑다운 방식으로 구현했는데 로직은

1. S==E 이면 팰린드롬

2. S+1 == E 일때 arr[S]==arr[E]이면 팰린드롬 다르면 X

3. arr[S]==arr[E]일때 D[S+1][E-1]가 1이면 팰린드롬 아니면 X

코드

#include<stdio.h>
#include<iostream>
#include<vector>
#include<queue>
#include<string>
#include<algorithm>
#include<memory.h>
 
using namespace std;
 
int arr[2001];
 
int d[2001][2001];
 
int go(int i, int j) {
    if (i == j)return 1;
    else if (i + 1 == j) {
        if (arr[i] == arr[j])return 1;
        else return 0;
    }
 
    if (d[i][j] >= 0) return d[i][j];
    if (arr[i] != arr[j]) return d[i][j] = 0;
    else return d[i][j] = go(i + 1, j - 1);
}
 
int main() {
 
    //freopen("Text.txt", "r", stdin);
 
    memset(d, -1, sizeof(d));
 
    int n,m;
    cin >> n;
 
    for (int i = 1; i <= n; i++) {
        scanf("%d",&arr[i]);
    }
 
    cin >> m;
 
    while (m--) {
        int start, end;
        scanf("%d %d", &start, &end);
 
        printf("%d\n", go(start, end));    
    }
 
}