[BOJ] 10942번 : 팰린드롬?

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

10942번: 팰린드롬?

dp문제이므로 테이블 설정을 잘 해주어야 한다. 

d[a][b]=k : a부터 b 팰린드롬이라면 k=1, 아니라면 k=0

 

우선, a부터 a는 항상 팰린드롬이다.

추가로 길이가 1 차이나는 a와 a-1는 서로 값이 같다면 팰린드롬이 된다. 

 

그리고 길이가 2 차이부터 n-1 까지 나는 숫자가 팰린드롬인지 검사해주면 된다. 

시작점이 s 이고 끝점이 e라면 두 숫자가 같으면서, 시작점과 끝점을 제외한 가운데 숫자가 팰린드롬이면 s부터 e는 팰린드롬에 해당된다. 

따라서 이런 사실을 바탕으로 코드를 작성하면 아래와 같다. 

 

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

int a[2005];
int d[2005][2005]; //d[a][b]=k : a~b까지 팰린드롬이라면 1, 아니라면 0

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

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

    for(int i=1; i<=n; i++){
        d[i][i]=1; //자기자신만은 팰린드롬임
        if(a[i-1]==a[i]) d[i-1][i]=1; //차이가 1 나는 애들 처리해줌
    }

    for(int gap=2; gap<n; gap++){ //차이가 2 나는 애들부터 n-1 까지 처리해줌
        for(int i=1; i<=n-gap; i++){
            int s=i, e=i+gap; //시작점은 i이고, 끝점은 i+gap임
            //시작점과 끝점이 같아야하고
            //시작점과 끝점을 제외한 가운데 숫자가 팰린드롬이어야함
            if(a[s]==a[e] && d[s+1][e-1]) d[s][e]=1; 
        }
    }

    int tc; cin>>tc;
    while(tc--){
        int s,e; 
        cin>>s>>e;
        cout<<d[s][e]<<'\n';
    }

    return 0;
}