#include <iostream>
using namespace std;
int num[2001];
int d[2001][2001];
int pellin(int i, int j)
{
    if (d[i][j] >= 0)
    {
        return d[i][j];
    }
    if (i == j)
    {
        d[i][j] = 1;
        return d[i][j];
    }
    if (i + 1 == j)
    {
        if (num[i] == num[j])
        {
            d[i][j] = 1;
        }
        else
            d[i][j] = 0;
        return d[i][j];
    }
    if (pellin(i + 1, j - 1) == 1)
    {
        if (num[i] == num[j])
        {
            d[i][j] = 1;
            return d[i][j];
        }
        else
        {
            d[i][j] = 0;
            return d[i][j];
        }
    }
    else
    {
        d[i][j] = 0;
        return d[i][j];
    }
}
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> num[i];
    }
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            d[i][j] = -1;
        }
    }
    int m;
    cin >> m;
    for (int i = 0; i < n; i++)
    {
        for (int j = i; j < n; j++)
        {
            pellin(i, j);
        }
    }
    for (int i = 0; i < m; i++)
    {
        int s, e;
        cin >> s >> e;
        cout << d[s - 1][e - 1] << "\n";
    }
    return 0;
}

문제 접근

어떤 수열의 부분 수열이 팰린 드롬인지 확인하는 문제이다.

해결 방법

다이내믹과 재귀 호출을 이용한다.
D[i][j] = A[i] ~ A[j] 가 팰린드롬이면 1, 아니면 0
초기화 -> 길이 1일떄는 반드시 팰린드롬. 길이 2일때는 두수가 같을 때 팰린드롬.