백준 / 10942 / 팰린드롬? / C++

문제 링크 : https://www.acmicpc.net/problem/10942

#include <bits/stdc++.h>

using namespace std;

vector<vector<bool>> dp;
vector<int> tmparr;

/*bool func(int start, int end)
{
    while(start <= end)
    {
        if(tmparr[start] == tmparr[end])
        {
            start++;
            end--;
        }
        else
        {
            return false;
        }
    }
    return true;
}*/

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    //freopen("test.txt", "rt", stdin);
    int n;
    cin >> n;
    dp.resize(n + 1, vector<bool>(n + 1));
    tmparr.resize(n + 1);
    for (int i = 1; i < n + 1; i++)
    {
        cin >> tmparr[i];
    }

    for (int i = 1; i < n + 1; i++)
    {
        dp[i][i] = true;
        if (i < n && tmparr[i] == tmparr[i + 1])
        {
            dp[i][i + 1] = true;
        }
    }

    for (int leng = 3; leng <= n; leng++)
    {
        for (int i = 1; i <= n - leng + 1; i++)
        {
            int j = i + leng - 1;
            if (tmparr[i] == tmparr[j] && dp[i + 1][j - 1])
            {
                dp[i][j] = true;
            }
        }
    }

    /*for(int i = 1; i < n + 1; i++)
    {
        for(int j = i; j < n + 1; j++)
        {
            dp[i][j] = func(i - 1,j - 1);
        }
    }*/
    int m;
    cin >> m;
    while(m--)
    {
        int x,y;
        cin >> x >> y;
        cout << (dp[x][y] ? 1 : 0) << "\n";
    }
    /*for (int i = 1; i < n + 1; i++)
    {
        for (int j = 1; j < n + 1; j++)
        {
            cout << (dp[i][j] ? 1 : 0) << " ";
        }
        cout << "\n";
    }*/
    return 0;
}

입력되는 수열 크기를 봤을 때 dp로 풀지 않으면 시간초과가 날 것 같아서 일단은 각 인덱스가 판별하는 수열의 시작 / 끝 인덱스를 의미하는 이차원 bool배열 dp를 선언하고, func라는 함수에 시작 / 끝 인덱스를 파라미터로 전달, return 값을 메모한 후 출력만 하려 했으나...

시간초과를 바로 먹은 후 생각해 보니 그냥 판별해야 하는 값을 바로 func에 넣어도 똑같은 코드였음을 알아챘다. 애초에 dp식으로 풀지 않았던 것이다.

그래서 팰린드롬 수열에 대한 점화식을 생각해 보았고, 판단해야 하는 수열의 길이가 1이면 당연히 true, 길이가 2라면 두 수가 같다면 true이고 길이가 3 이상이라면 시작과 끝 값을 제외한 부분이 팰린드롬인가, 그리고 시작 값과 끝 값이 같은가. 이 2가지를 판단하면 된다는 것을 알았다.

길이가 1,2인 수열에 대한 판별값을 초기값으로 입력한 후, 길이가 3 이상인 수열에 대해 위에서 생각했던 알고리즘을 구현했더니 AC를 받았다.