[백준][C++] 10942: 팰린드롬?

문제

풀이

• 다이나믹 프로그래밍 문제로 S와 E가 입력될 때마다 처음부터 검사하면 시간초과이다.
• S와 E가 같다면 무조건 팰린드롬이다. 
• S와 E가 1차이라면 num[S]와 num[E]만 검사하면 된다. 
• S와 E에서부터 시작해서 num[S]와 num[E]가 같으면서 사이의 수열이 팰린드롬이라면 그 수열은 팰린드롬이다. 
• 여기서 S와 E의 값을 각각 1늘리고 1줄이는 방식으로 검사하면서 num[S]와 num[E]가 같지않다면 그 수열은 팰린드롬이 아니다.
• '\n' 을 사용해야 한다. endl을 사용할 경우 시간초과가 발생한다.

코드

#include <iostream>

using namespace std;

bool cache[2001][2001];
int num[2001];

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(nullptr);

    int N, M;

    cin >> N;
    for (int i = 1; i <= N; ++i)
    {
        cin >> num[i];
    }

    cin >> M;

    // S와 E가 같다면 true
    for (int i = 1; i <= N; ++i)
    {
        cache[i][i] = true;
    }

    // E == S + 1일 경우 두 수만 비교해서 같다면 true
    for (int i = 1; i < N; ++i)
    {
        if (num[i] == num[i + 1])
        {
            cache[i][i + 1] = true;
        }
    }

    while (M--)
    {
        int S;
        int E;
        cin >> S >> E;

        // 양 끝에서 부터 검사를 시작
        // S에서의 값과 E에서의 값이 같으면서 그 사이의 수열이 팰린드롬이면 S와 E까지의 수열도 팰린드롬이다.
        // 점점 가운데로 향하면서 검사
        int temp_start = S;
        int temp_end = E;
        while (temp_start <= temp_end)
        {
            if (num[temp_start] == num[temp_end] && cache[temp_start][temp_end] == 1)
            {
                cache[S][E] = true;
                break;
            }
            else if (num[temp_start] != num[temp_end])
            {
                cache[S][E] = false;
                break;
            }

            temp_start++;
            temp_end--;
        }

        cout << cache[S][E] << '\n';
    }

    return 0;
}