백준 10942: 팰린드롬?

1 2 1 과 같이 대칭되는 숫자인지 판별하는 문제

다이나믹프로그램을 활용한다. d[i][j] 를 i번째 수 부터 j 번째가 팰린드롬인지 여부라고한다면 재귀로 d[i+ 1][j - 1]을 다이나믹으로 문제의 범위를 좁혀나가준다. 팰린드롬은 사실 n정도의 시간복잡도로 구해 줄 수 있지만 문제에서 엄청난 수의 문제를 구하라고 하기 때문에 문제의 정답을 기억해놓고 다시 써먹어야할 필요성이있다. 그래서 다이나믹을 활용하는 것이다.

#include <iostream>
#include <cstring>
using namespace std;
int a[2001];
int d[2001][2001];
int n, q;
 
int go(int start, int end)
{
    if (start == end)
    {
        return 1;
    }
    if (start + 1 == end){
        if (a[start] == a[end]){
            return 1;
        }
        else
            return 0;
    }
    if (d[start][end] != -1)
        return d[start][end];
    if (a[start] != a[end])
        return d[start][end] = 0;
    else return d[start][end] = go(start + 1, end - 1);
}
 
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n;
    for (int i = 1; i <= n; ++i)
        cin >> a[i];
    cin >> q;
    memset(d, -1, sizeof(d));
    int s, e;
    while (q != 0)
    {
        cin >> s >> e;
        cout << go(s ,e) << '\n';
        --q;
    }
    return 0;
}