[Baekjoon,10942] 팰린드롬?

무식하게 접근

어떻게 부분 문제로 나누어 동적 계획법을 적용할 수 있을 지 많이 고민했다. 처음 접근은 동적 계획법을 적용하지 않고 무식하게 해결하는 것이었다. 주어진 구간 [s,e]에 대해 수열 perm[]이 팰린드롬인지 한 칸 씩 인덱스를 가운데로 모으며 판단하는 것이다. 이를 구현하면 아래와 같은 함수가 될 것이다.

int bruteForce(int s, int e)
{
    for(int i=s;i<(s+e)/2;++i)
        if(perm[i]!=perm[e-(i-s)])
            return false;
    return true;
}

하지만 이 방법은 최악의 경우 1,000,000 x 1,000회 반복되어 제한 시간(0.5초)내에 돌아갈 수 없다.

다시 사용될 값을 저장하자

위 방법에서 보면 알 수 있듯이 특정한 구간이 이미 팰린드롬이라고 판정된 경우 다시 중복하여 계산할 필요가 없다. 따라서 이미 판정된 경우 해당 구간에 대해 이를 저장하여 다시 사용하면 된다.

이를 구현한 코드를 아래에서 볼 수 있다. 직관적으로 구현하기 위해 재귀로 구현했다. 순서가 뒤 바뀔 때까지 양 끝 위치의 숫자가 같다면 팰린드롬이라고 판정하였고 이를 cache[][]에 저장하였다. 주의할 점은 입출력 값이 많기 때문에 빠른 입출력 함수를 이용해야 한다는 것이다.

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

const int MAX=2000;

int N;
int perm[MAX];
int cache[MAX][MAX];

int dp(int lo, int hi)
{
    // 기저 사례: 순서가 뒤 바뀔 때까지 같았다.  
    if(lo>=hi)
        return 1;
    
    int& ret=cache[lo][hi];
    if(ret!=-1)
        return ret;
    
    // 중간에 하나라도 회문이 아니면 회문이 안됨.
    if(perm[lo]==perm[hi])
        return ret=dp(lo+1,hi-1);
    return ret=0;
}

int main()
{
    cin>>N;
    for(int i=0;i<N;++i)
        scanf("%d",&perm[i]);
    
    memset(cache,-1,sizeof(cache));
    
    int m;
    cin>>m;
    while(m--)
    {
        int s,e;
        scanf("%d %d",&s,&e);
        --s;--e;
        printf("%d\n",dp(s,e));
    }
    
    return 0;
}