BOJ 10942 팰린드롬?

문제 링크 : https://www.acmicpc.net/problem/10942

10942번: 팰린드롬?

 

문제에 포함된 예를 보자.

1. Top-Down

길이가  \( l \) 인 수열이 팰린드롬인지 여부는 양끝을 조사해서 다르면 그대로 종료하고,

같으면 양끝을 제거한 \( l-2 \) 인 수열을 살펴보면 된다.

 

#include<bits/stdc++.h>

using namespace std;

int arr[20001], dp[2001][2001];

int recur(int s,int e){
    if(s==e) return 1;
    if(s+1==e) {
        if(arr[s]==arr[e]) return 1;
        else return 0;
    } 
    
    int &ret=dp[s][e];
    if(ret!=-1) return ret;
    
    if(arr[s]==arr[e]) return ret=recur(s+1,e-1);
    return ret=0;
}

int main(){
    memset(dp, -1, sizeof dp);
    int n; scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&arr[i]);
    int m; scanf("%d",&m);
    while(m--){
        int a,b; scanf("%d%d",&a,&b);
        printf("%d\n", recur(a,b));
    }
}

 

recur 함수 내에서 분기가 최대 2 개이고 순서쌍 (i,j) 는 \(O (n^2) \) 이므로 전체적으로 \(O (n^2) \) 로 동작.

 

 

2. Bottom-Up

 

길이를 1, 2, 3, ... 차례로 늘려가면서 앞서서 구해둔 짧은 길이 수열의 정보를 이용.

 

#include<bits/stdc++.h>

using namespace std;

int arr[2001], dp[2001][2001];

int main(){
    memset(dp,-1,sizeof dp);
    int n; scanf("%d",&n);
    for(int i=1;i<=n;i++) {
        scanf("%d",&arr[i]);
        dp[i][i]=1;
        dp[i-1][i]=arr[i-1]==arr[i]?1:0;
    }
    
    for(int l=3;l<=n;l++){
        for(int i=1;i+l-1<=n;i++){
            int e=i+l-1;
            if(arr[i]==arr[e])
                dp[i][e]=dp[i+1][e-1];
            else
                dp[i][e]=0;
        }
    }
    
    int m; scanf("%d",&m);
    while(m--){
        int a,b; scanf("%d%d",&a,&b);
        printf("%d\n", dp[a][b]);
    }
}

 

for 루프가 두 번 충첩되어 있으므로 \( O(n^2 )\) 으로 동작.

 

덜렁거리는 성격이라 dp 초기화와 관련된 실수가 잦은데... 정신차리자.