[백준 c++] 10942 팰린드롬?

문제

https://www.acmicpc.net/problem/10942
N개의 자연수가 주어지고 M개의 질문이 주어진다.
질문은 S번 째 수부터 E번 째 수까지 팰린드롬을 이루는지 물어보는 것이다.
각 질문의 답을 출력하라

---

풀이

이 방법은 1 ≤ N ≤ 2,000 이고, 1 ≤ M ≤ 1,000,000 이므로 최악의 경우 2,000* 1,000,000 = 2,000,000,000 (20억번)의 연산 횟수가 발생한다.

따라서 시간복잡도를 줄이기 위해 dp를 이용해서 모든 s,e에 대한 팰린드롬을 구해서 풀어야 한다.

규칙을 찾기 위해 테스트케이스로 각 출발지에 대해 팰린드롬 여부를 작성해봤다.
dp[i][j]가 팰린드롬이 되기 위해선 dp[i+1][j-1]이 팰린드롬을 이뤄야함을 알 수 있다.

먼저 작은 범위로 팰린드롬을 이루는 dp부터 작성해준다.
1개짜리는 모두 팰린드롬이다.
2개짜리는 두 수가 같으면 팰린드롬이다.

3개짜리부터는 양 끝의 수가 같고 dp[i+1][j-1] = 1이면 팰린드롬이다.

---

코드

#include <iostream>
#include <algorithm>
using namespace std;
int n, m, s, e, a[2001], dp[2001][2001];

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        dp[i][i] = 1;
    }
    for (int i = 1; i < n; i++)
    {
        if (a[i] == a[i + 1])
            dp[i][i + 1] = 1;
    }
    for (int i = 3; i <= n; i++)
    {
        for (int j = i - 2; j >= 1; j--)
        {
            if (a[i] == a[j] && dp[j + 1][i - 1])
                dp[j][i] = 1;
        }
    }
    cin >> m;
    for (int i = 0; i < m; i++)
    {
        cin >> s >> e;
        cout << dp[s][e] << "\n";
    }
}