10942번

10942번 - 팰린드롬?

DP를 이용해서 문제를 풀었다, 처음에는 그냥 하나 하나 완전탐색으로 하려고 했더니,

최대로 계산했을 때, 앞에서 N개 보고, 뒤에서 N개 보면서 확인 = 2N 번

거기에 질문 M 개가 있으므로 O(2MN) 이 되는데, MN=10억이라는 숫자가 나오기 때문에 1초안에 풀 수 없었다.

그래서 DP를 이용해서 문제를 풀었다.

D[S][E] = 팰린드롬이면 1, 아니면 0 이라는 점화식을 세웠다.

나는 보통 DP는 재귀로 풀기 때문에, 재귀는 줄여나가는게 핵심이다.

그래서 D[S][E] 가 팰린드롬인지 확인할 때, D[S][E] 가 팰린드롬이 되기 위해서는

 D[S+1][E-1] 에서 V[S] 와 V[E] 가 같으면 팰린드롬이 된다는 사실을 알았고, 이를 통해 글자길이를 줄여나가면서 캐시에 저장하였다.

s 가 e 보다 커지는 경우는 팰린드롬이기 때문에 1을 리턴,

D 값을 -1로 초기화 해놨기 때문에 , D 값이 0 이상이면 캐시에 저장된 값으로 인지하고 리턴 해주는 방식으로 문제를 풀었다.

<정답 코드>

#include<iostream>
#include<vector>
#include<string.h>
 
using namespace std;
int D[2001][2001];
vector<int> v;
int N, M;
 
int go(int s, int e)
{
    if (s > e)
    {
        return 1;
    }
    
    if (D[s][e] >= 0)
    {
        return D[s][e];
    }
 
    if(v[s]==v[e])
    { 
        D[s][e] = go(s + 1, e - 1);
    }
    else
    {
        D[s][e] = 0;
    }
 
    return D[s][e];
 
}
int main()
{
    
    scanf("%d",&N);
    memset(D, -1, sizeof(D));
    v.resize(N + 1);
 
    for (int i = 1; i <= N; i++)
    {
        scanf("%d", &v[i]);
    }
 
    cin >> M;
 
    while (M--)
    {
        int S, E;
        scanf("%d %d", &S, &E);
 
        printf("%d\n", go(S, E));
    }
    return 0;
}