[10942] 팰린드롬?

http://boj.kr/10942

DP - basic

d[i][j] = i~j 까지가 팰린드롬인지.

< 소스코드 >

#include <stdio.h>
#include <string.h>
 
int p[2001];
int d[2001][2001];
 
int isP(int s, int e)
{
    int i;
    if(s >= e) return 1;
    if(d[s][e] != -1) return d[s][e];
    if(p[s] != p[e]) return 0;
    return d[s][e] = isP(s+1, e-1);
}
 
int main()
{
    int i, j, n, m;
    scanf("%d", &n);
 
    for(i=1; i<=n; i++)
        scanf("%d", p+i);
 
    memset(d, -1, sizeof(d));
 
    scanf("%d", &m);
    while(m--) {
        int a, b;
        scanf("%d%d", &a, &b);
        printf("%d\n", isP(a, b));
    }
 
    return 0;
}

>> 모든 경우를 다 구해놓고 하려다가 시간만 쓰고, 머리만 쓴거 같다.

>> 쿼리마다 필요한걸 구하면서 그때 구한걸 저장해(메모이제이션) 놓으면 된다..

< 바텀업 >

#include <cstdio>
int n;
int a[2000];
bool d[2000][2000];
int main() {
    scanf("%d",&n);
    for (int i=0; i<n; i++) {
        scanf("%d",&a[i]);
    }
    for (int i=0; i<n; i++) {
        d[i][i] = true;
    }
    for (int i=0; i<n-1; i++) {
        if (a[i] == a[i+1]) {
            d[i][i+1] = true;
        }
    }
    for (int k=3; k<=n; k++) {
        for (int i=0; i<=n-k; i++) {
            int j = i+k-1;
            if (a[i] == a[j] && d[i+1][j-1]) {
                d[i][j] = true;
            }
        }
    }
    int m;
    scanf("%d",&m);
    while (m--) {
        int s, e;
        scanf("%d %d",&s,&e);
        printf("%d\n",d[s-1][e-1]);
    }
    return 0;
}

>> 과거 AC 받은 코드인데, 백준님 코드 같다.. 내스타일의 코드는 아니므로...

>> 길이가 1인 부분수열은 반드시 팰린드롬이다.

>> 길이가 2인 부분수열은 두 수가 같을때만 팰린드롬이다.

>> d[i][j] 가 팰린드롬이려면 a[i] == a[j] 이고 d[i+1][j-1] 이 팰린드롬이여야 한다.