[BOJ] #10942 팰린드롬?

시간 제한	메모리 제한	정답 비율
0.5 초	256 MB	28.087%

10942번: 팰린드롬?

 

문제

해결

key point, 길이가 1, 2, ... N 까지 팰린드롬인지 확인한다. DP

• 길이가 1일 때는 모두 팰린드롬
• 길이가 2일 때는 i, j 양 끝이 같아야 팰린드롬
• 길이가 3이상일 때는 i, j 양 끝이 같으면서 dp[i+1][j-1]이 true이면 팰린드롬이다.

 

코드(재귀)

메모리	시간
17664 KB	300 ms

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<algorithm>
using namespace std;
int arr[2001];
int dp[2001][2001];
int n, m;
int go(int i, int j) {
    int& ret = dp[i][j];
    if (i == j) {
        ret = 1;
        return ret;
    }
    if (i + 1 == j) {
        if (arr[i] == arr[j]) {
            ret = 1; return ret;
        }
        else {
            ret = 0; return 0;
        }
    }
    if (ret > 0)return ret;
    if (arr[i] != arr[j]) {
        ret = 0; return ret;
    }
    else return ret = go(i + 1, j - 1);
}
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &arr[i]);
    memset(dp, -1, sizeof(dp));
    scanf("%d", &m);
    while (m--) {
        int s, e;
        scanf("%d %d", &s, &e);
        printf("%d\n", go(s, e));
    }
 
    return 0;
}

 

코드(반복문)

메모리	시간
5028 KB	300 ms

#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;
}