백준 10942 팰린드롬?

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

문제와 채점은 위 사이트에서 확인 하실 수 있습니다

 

이 문제는 수열이 주어졌을때 구간에 대한 팰린드롬 여부를 출력해야 하는 문제입니다.

수열의 길이는 2000 이고 총 100만개의 쿼리가 들어오므로 모든 구간에 대한 팰린드롬 여부를 미리 구해놓아야 합니다. 따라서 저는 2차원 dp배열을 선언하고 재귀함수를 호출하는 식으로 구했습니다.

 

길이가 1일때와 2일때는 미리 구해야 하는데 길이가 1인경우는 항상 팰린드롬이므로 1을 저장합니다.

길이가 2일때는 두문자가 같다면 팰린드롬이므로 1을 저장하고 그렇지 않으면 팰린드롬이 아니므로 0을 저장합니다.

 

이후 구간의 양끝에서부터 길이를 줄여나가면서 찾으면 됩니다.

현재 함수에서 보는 구간이 s,t라고 하면 s와 t의 문자가 동일하고 dp[s-1][t-1]이 팰린드롬이라면 이 문자도 팰린드롬임을 알 수 있습니다. 모든 경우를 구하는데는  O(N^2)의 시간이 걸립니다.

 

다음은 코드입니다.

 

#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

int number[2001];
int dp[2001][2001];

int sol(int start, int end) {

    int &ret = dp[start][end];
    if(ret != -1) return dp[start][end];

    sol(start+1, end);
    sol(start, end-1);
    int flag = sol(start+1, end-1);
    if(number[start] == number[end] && flag)
        ret = 1;
    else
        ret = 0;
    return ret;
}

int main(void) {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int N; cin >> N;
    memset(dp, -1, sizeof(dp));
    for(int i = 0; i < N; i++)
        cin >> number[i];
    for(int i = 0; i < N; i++) {
        if(i < N-1) { //길이 2인경우
            if(number[i] == number[i+1])
                dp[i][i+1] = 1;
            else
                dp[i][i+1] = 0;
        }

        dp[i][i] = 1; //길이 1인경우
    }

    sol(0, N-1);
    int M; cin >> M;
    while(M--) {
        int S,E; cin >> S >> E;
        cout<<dp[S-1][E-1]<<'\n';
    }
    return 0;
}