[C++] 백준 10942 [팰린드롬?]

접근방식

DP로 접근하면 되는 문제이다.

팰린드롬이란?

팰린드롬이란 앞에서 읽으나 뒤에서 읽으나 같은 숫자를 의미한다.

점화식 작성

다음과 같이 팰린드롬인 숫자들의 집합이 있다고 하자.

1 2 3 4 3 2 1

이 집합이 팰린드롬인지 아닌지 재귀적으로 판별하려면 다음과 같은 두가지 조건을 만족시키면 된다.

1) 양 끝 숫자가 같아야한다.
앞에서 읽으나 뒤에서 읽으나 같아야함으로 양 끝 숫자가 같아야 함은 자명하다.

2) 양 끝 숫자를 제거한 숫자들의 집합이 팰린드롬이어야한다.

그러면 점화식은 다음과 같다.

is_pal(i,j) = (num[i] == num[j]) && is_pal(i+1, j-1)

여기서 is_pal은 팰린드롬을 판별하는 return형이 bool인 함수이고, num은 숫자들의 집합을 의미한다.

점화식의 초기조건

이 문제의 조건은 i < j이다. 즉, i >= j일때 종료시켜주면 된다.
위 점화식에서 && 조건이기 때문에 num[i]와 num[j]가 같지 않다면 is_pal 부분까지 계산하지 않고 바로 false를 반환한다.
i >= j인 상태까지 왔다면 펠린드롬임이 자명하다.
그러므로 초기조건은 i >= j일때 true를 반환하면 된다.

소스코드

#include<iostream>
#include<vector>

using namespace std;

int pal[2001][2001];
vector<int> num;

bool is_pal(int S, int E){
    if(S >= E) return true;
    int& ret = pal[S][E];
    if(ret == -1){
        ret = (is_pal(S+1, E-1) && (num[S] == num[E]));
    }
    return ret;
}

int main(){
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    for(int i=0; i<2001; i++){
        for(int j=0; j<2001; j++){
            pal[i][j] = -1;
        }
    }
    int N,M;
    cin >> N;
    num = vector<int>(N);
    for(int i=0; i<N; i++) cin >> num[i];
    cin >> M;
    while(M--){
        int S,E;
        cin >> S >> E;
        cout << is_pal(S-1,E-1) << "\n";
    }
}