BOJ - 10942 팰린드롬?

수열이 주어지고 시작점과 끝점이 주어졌을 때 두 점 사이의 수열이 팰린드롬인지 판단하는 문제이다.

문제풀이 전략

우선 팰린드롬이란 가운데 수를 기준으로 대칭이 되는 수열을 의미한다.

1 2 3 2 1 과 같은 경우를 팰린드롬 이라고 한다.

팰린드롬인지 판단하는 방법은 가장 기본적으로 O(n)의 시간복잡도로 구할 수 있다.

하지만 팰린드롬인지 판단해야 하는 경우가 최대 1,000,000으로 O(n)을 사용한다면 최악의 경우 1,000,000 x 2000 이 되므로 시간초과가 날 것이다.

따라서 O(n)의 방법으로 푸는 것은 무리다.

팰린드롬의 특징은 양 끝 점을 제외하더라도 사이 부분이 팰린드롬을 유지한다.

위의 예시처럼 1 2 3 2 1 의 경우 양 끝 점을 제외한 2 3 2 역시 팰린트롬을 유지한다.

즉, 주어진 시작점 s 와 끝점 e가 서로 같을 때 s+1 ~ e-1 까지가 팰린드롬이라면 s ~ e 역시 팰린드롬임을 판단할 수 있다.

이 과정을 dp를 사용하여 풀 수 있다.

코드

#include<iostream>
#include<vector>

using namespace std;

int n;
int m;
vector<int> v;
int dp[2001][2001];
int main(){
    cin.tie(NULL);
    cout.tie(NULL);
    ios_base::sync_with_stdio(false);

    cin >> n;
    v.push_back(-1);
    for(int i=1;i<=n;i++){
        int tmp;
        cin >> tmp;
        v.push_back(tmp);
        dp[i][i] = 1;
    }

    for(int i=1;i<n;i++){ // 파악 갯수
        for(int j=1;j<=n-i;j++){ // 각 경우
            if(v[j] == v[j+i]){
                if(i == 1 || dp[j+1][j+i-1] == 1) // 길이가 2 이거나 j+1,j+i-1일때 팰린드롬이면
                    dp[j][j+i] = 1;
            }
        }
    }

    cin >> m;
    for(int i=0;i<m;i++){
        int s,e;
        cin >> s >> e;
        cout << dp[s][e] << "\n";
    }
}

출처
https://www.acmicpc.net/problem/10942

회고
처음 생각은 단순히 i=1~n-1 / j=i+1~n 로 2중 반복문을 돌리려 했는데, 이런 방식을 사용한다면 조건절의 dp[i+1][j-1] 의 값이 아직 세팅되어 있지 않으므로 틀린 답을 도출해 낸다.

그래서 갯수를 정할 부분과, 각 지점으로 반복문을 돌렸다.