[백준 10942] 팰린드롬?

[ghdcksgml1]

문제

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

[문제설명]

숫자와 구간이 주어졌을 때 그 구간이 팰린드롬인지 0과 1로 나타내는 문제로

1<=N<=2,000까지 숫자가 주어지는데 구간은 1<=M<=1,000,000이라서

구간이 주어질때마다 팰린드롬인지 체크하는 시간복잡도는 O(N*M)으로 상당한 비용을 가진다.

따라서, [S,E]에 대한 팰린드롬여부 정보를 미리 저장해두고, 쿼리가 주어질때마다 리턴해주면 쿼리의 시간복잡도는 O(M*1)이 된다.

dp[2001][2001]에 [S,E] 정보를 넣어줘야하는데 어떻게 구할지 생각해보는데 팰린드롬의 특징을 하나 발견함

v = {1, 2, 1, 3, 1, 2, 1 }숫자가 있을때 팰린드롬인지를 파악하기 위해 양쪽끝에서 하나씩 줄여나가며 팰린드롬인지를 체크한다.

v[0] == v[6], v[1] == v[5], v[2] == v[4], v[3] == v[3] 이므로 팰린드롬이고, 여기서 v[0] == v[6]이더라도 나머지 [1,5] 가 모두 팰린드롬이여야 해당 배열이 팰린드롬이 된다.

여기서 dp를 이용하려면 [1,5]의 정보를 가지고 있다면? [1,5]가 팰린드롬이면 v[0] == v[6]이므로 v 배열은 팰린드롬이 되고, [1,5]가 팰린드롬이 아니라면 v[0] == v[6]이라도 팰린드롬이 아닌 배열이 된다.

또다른 특징은, v = {1, 2, 1, 3, 1, 2, 3 } 이라면, v[0] != v[6]일 경우 나머지 구간을 체크하지 않아도 팰린드롬이 아닌것을 확인할 수 있다.

위 두가지 특징을 이용해 dp를 짜보면, 다음과 같이 탑다운 재귀형식으로 코드를 짤 수 있다.

int solve(int S,int E){ // 시작과 끝, dp는 -1로 초기화 되어있음.
    if(dp[S][E] != -1) return dp[S][E]; // 팰린드롬 여부가 저장되어 있으면 바로 리턴
    if(v[S] != v[E]) return dp[S][E] = 0; // v[S] != v[E]이라면 두번째 특징을 통해 0인걸 알 수 있음
    else{
        if(S > E) return dp[S][E] = 1; // S가 E보다 큰 경우에는 1을 리턴
        return dp[S][E] = solve(S+1, E-1); // v[S] == v[E]이라면, 안쪽 수들도 모두 팰린드롬이여야하므로 재귀호출을 통해 알아본다.
    }
}

시간복잡도

시간복잡도는 dp[S][E]를 만드는데 O(N²)이 걸린다.

소스코드

// 언어 : C++ , (성공/실패) : 1/0 , 메모리 : 2024 KB , 시간 : 0ms
#include <iostream>
#include <vector>
#include <algorithm>
#include <string.h> // memset

#define ALL(x) begin(x), end(x)
#define pll pair<ll,ll>
#define pii pair<int,int>
#define xx first
#define yy second
#define MAX 1e6

using namespace std;
typedef long long ll;

vector<int> v;
int dp[2001][2001];

int solve(int S,int E){
    if(dp[S][E] != -1) return dp[S][E];
    if(v[S] != v[E]) return dp[S][E] = 0;
    else{
        if(S > E) return dp[S][E] = 1;
        return dp[S][E] = solve(S+1, E-1);
    }
}

int main(void){
    // 입출력 속도 최적화
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int N; cin>>N;
    v.push_back(0);
    for(int i=0;i<N;i++){
        int tmp; cin>>tmp;
        v.push_back(tmp);
    }
    memset(dp,-1,sizeof(dp));
    for(int i=0;i<2001;i++){
        dp[i][i] = 1;
    }

    for(int i=1;i<=N;i++){
        for(int j=i;j<=N;j++){
            dp[i][j] = solve(i, j);
        }
    }

    int M; cin>>M;
    while(M--){
        int a,b; cin>>a>>b;
        cout<<dp[a][b]<<'\n';
    }

    return 0;
}