[BOJ] C++ 10942: 팰린드롬? - 테이블 채우는 순서를 주의하자!

10942번: 팰린드롬?

예제

7
1 2 1 3 1 2 1
4
1 3
2 5
3 3
5 7

ans :
1
0
1
1

---

문제를 보면 수는 2000개밖에 안되는데, 질문이 최대 백만 개다. 또 수의 최댓값이 백만이다. 질문의 수가 많고 시간이 0.5초밖에 안 돼서 질문이 들어오면 상수시간 안에 답해야 한다고 생각하고 풀이를 떠올려 봤다.

 

상수시간 안에 답하려면 브루트포스를 사용하면 될 것 같아서 이차원 테이블로 dp [i][j] = number [i] ~ number [j]까지 펠린드롬인지 저장해 두는 방향으로 가닥을 잡았다. 그런데 테이블을 채우는 게 또 관건이다. 펠린드롬에 대한 점화식을 이전/다음항을 이용해서 찾을 수 있으면 해결이 가능하다. 점화식 없이 수가 펠린드롬인지 판단하면 시간이 좀 애매해서 점화식으로 생각했다. 

이런 식으로 점화식을 찾았다. 간단하게 S ~~ P가 있으면 ~~ 가 팰린드롬이고 S와 P가 같다면 S ~~ P도 팰린드롬이라는 규칙을 이용해서 테이블링을 했다. 테이블을 채울 때 좀 헷갈렸는데 평소 하듯이 left -> right 순서로 채우면 테이블을 채울 수 없다. 따라서 top->bottom순으로 채웠는데, 구현이 헷갈린다면 이차원 배열의 인덱스를 써놓고 어떤 순서로 채울지 그려보면 잘 보인다.

 

1번 규칙을 찾는건 굉장히 쉬웠는데 떠올리자마자 이건 구현 안된다 싶었다. 여기서 조금만 생각을 바꾸면 2번 규칙을 찾을 수 있다.

/** DP 10942 팰린드롬? **/
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;

int n, m;
int num[2023];
int dp[2023][2023];

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

    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> num[i];

    cin >> m;

    // dp 초기값 세팅 [i][i]는 당연히 팰린드롬
    // [i][i+1]은 두 값이 같으면 팰린드롬
    for (int i = 1; i <= n; i++)
    {
        dp[i][i] = 1;
        if (num[i] == num[i + 1])
            dp[i][i + 1] = 1;
    }

    for (int col = 3; col <= n; col++)
        for (int row = 1; row <= col - 2; row++)
            if (num[col] == num[row] && dp[row + 1][col - 1])
                dp[row][col] = 1;

    while (m--)
    {
        int S, E;
        cin >> S >> E;
        cout << dp[S][E] << '\n';
    }
}