백준 문제 10942번 팰린드롬? 문제풀이 c++

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

10942번: 팰린드롬?

 

문제해설

 

dp로 풀었는데 dp[i][j]를 i번째부터 j번재까지의 문자열이 팰린드롬이라면 1 그렇지 않으면 0 으로 정의했다.

 

길이가 1인경우엔 무조건 1이고 길이가 2인 경우엔 두글자가 같으면 1이다 이것은 입력을 받을 때 바로 알 수있다.

또 팰린드롬글자의 앞뒤에 같은 글자를 붙이면 그것 역시 팰린드롬이라는 특성을 이용하면 dp배열을 채워 갈수가 있다.

 

이 아이디어로 다음과같이 코드를 작성하였다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int a[2005];
int dp[2005][2005];
int main(){
    cout.tie(NULL);
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    int n,m,s,e;
    cin>>n;
    for(int i=1; i<=n; i++)
    {
        cin>>a[i];
    }
    for(int i=1; i<=2000; i++)
    {
        dp[i][i]=1;
        if(a[i]==a[i+1])
        {
            dp[i][i+1]=1;
        }
    }
    for(int j=1998; j>=1; j--)
    {
        for(int i=1; i<=j; i++)
        {
            if((dp[i+1][i+2000-j-1]==1)&&(a[i]==a[i+2000-j]))
            {
                dp[i][i+2000-j]=1;
            }
        }
    }
    cin>>m;
    while(m--)
    {
        cin>>s>>e;
        cout<<dp[s][e]<<"\n";
    }
}