Baekjoon 10942 (팰린드롬?)

Baekjoon 10942, 백준 10942 문제의 본인 풀이입니다!
문제는 아래의 링크에서 확인할 수 있습니다.
문제보기

#include <cstdio>
#include <cstring>

using namespace std;

int arr[2002];
// dp[S][E]: check if arr[S] to arr[E] is pelindrome
// dp = -1 : not visited, 0 : not pelindrome, 1 : pelindrome
int dp[2002][2002];

void func(int S, int E){
    int s = S, e = E;
    while(s <= e && s >= S && e <= E){
        // one number : pelindrome
        if( s == e ) {
            dp[s][e] = 1;
            s--;
            e++;
            continue;
        }

        // adjacent number : should be same
        else if( e - s == 1 ){
            if(arr[s] == arr[e]) {
                dp[s][e] = 1;
                s--;
                e++;
                continue;
            }

            else {
                dp[s][e] = 0;
                s--;
                e++;
                continue;
            }
        }

        // if we already visited dp[s][e], break
        else if(dp[s][e] != -1) break;

        // if we don't know dp[s+1][e-1] either
        else if(dp[s+1][e-1] == -1){
            s++;
            e--;
            continue;
        }

        // if arr[S+1] to arr[E-1] is pelindrome and arr[S]==arr[E], arr[S] to arr[E] is pelindrome
        else if( dp[s+1][e-1] == 1 && arr[s] == arr[e]) {
            dp[s][e] = 1;
            s--;
            e++;
            continue;
        }

        // else: not pelindrome
        else {
            dp[s][e] = 0;
            s--;
            e++;
            continue;
        }
    }

    // print
    if(dp[S][E] == 1)
        printf("1\n");

    else if(dp[S][E] == 0)
        printf("0\n");
}

int main() {
    // input
    int N, M;
    scanf("%d",&N);
    for(int i = 1; i <= N; i++){
        scanf("%d",&arr[i]);
    }

    scanf("%d",&M);

    // solution
    memset(dp, -1, sizeof(dp)); // original value of dp is all -1

    while(M--){
        int S, E;
        scanf("%d %d", &S, &E);
        func(S, E);
    }
}

마찬가지로 dp 배열의 -1 값을 통해 방문 여부를 따졌다.
이번에는 memset(dp, -1, sizeof(dp))를 이용하여 dp의 초기값을 -1로 설정해 보았다.
memset 을 이용하기 위해서는 #include <cstring> 을 해야 한다는 점을 잊어서는 안 된다.

dp[i][j] 를 ‘ i 부터 j 까지가 팰린드롬인가? ‘ 를 확인하는 배열로 두고,
팰린드롬의 귀납적 성질 ( 양끝 값이 같고, 그 사이가 팰린드롬이면 전체도 팰린드롬이다 ) 을 이용하여 해결한
전형적인 동적계획법 문제였다.