[백준/BOJ] 10942번 팰린드롬? (C++)

www.acmicpc.net/problem/10942

10942번: 팰린드롬?

어려운 DP문제였습니다. (다시 풀기)

일반적으로 팰린드롬인지 확인하는 과정은 맨 앞과 맨 뒤, 두번째와 뒤에서 두번째, 세번째와 뒤에서 세번째 이런식으로 문자가 같은지 확인하므로 O(N)의 시간 복잡도가 소요됩니다. 그런데 여기서 수열의 크기가 최대 2,000이고 질문의 개수가 최대 1,000,000 이기 때문에, O(N*M) = 2,000,000,000 으로 시간초과가 발생할 수 있습니다. 따라서 DP로 접근하여 문제를 해결해야합니다.

 

질문마다 s와 e에 따른 팰린드롬의 확인여부는 다음과 같은 케이스를 가집니다.

1. 팰린드롬의 길이가 1인 경우 : 한자리이므로, 항상 팰린드롬이 됩니다.

2. 팰린드롬의 길이가 2인 경우 : 앞과 뒤가 같으면 팰린드롬이 됩니다.

3. 팰린드롬의 길이가 3이상인 경우 : 맨 앞과 맨 뒤가 같으면서 둘을 제외한 나머지 부분이 팰린드롬이면 팰린드롬이 됩니다.

 

#include <iostream>
#include <vector>
using namespace std;

bool dp[2001][2001]; // s~e는 팰린드롬인가?

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    int n, m;
    cin >> n;
    vector<int> v(n + 1);
    
    for(int i = 1; i <= n; i++) {
        cin >> v[i];
    }
    
    // 팰린드롬 길이 == 1
    for(int i = 1; i <= n; i++) {
        dp[i][i] = true;
    }
    
    // 팰린드롬 길이 == 2
    for(int i = 1; i <= n - 1; i++) {
        if(v[i] == v[i + 1]) dp[i][i + 1] = true;
    }
    
    // 팰린드롬 길이 >= 3
    for(int len = 3; len <= n; len++) {
        for(int i = 1; i <= n - len + 1; i++) {
            int j = i + len - 1;
            if(v[i] == v[j] && dp[i + 1][j - 1]) dp[i][j] = true;
        }
    }
    
    cin >> m;
    for(int i = 1; i <= m; i++) {
        int s, e;
        cin >> s >> e;
        if(dp[s][e]) cout << "1\n";
        else cout << "0\n";
    }
}