[백준 10942] 팰린드롬? [C]

백준 - 10942

---

풀이

Dynamic Programming의 Memorization 방식으로 풀이했다.

(S~E) 구간이 팰린드롬인지 알기 위해서는 (S+1 ~ E-1), (S+2 ~ E-2), ... (X, X+1) or (X, X)구간의 수들이 팰린드롬인지 알아내는 과정을 반복해야한다.

 

길이가 3이상일 때, 요소가 홀수개인 팰린드롬은 최종적으로 길이가 1인 팰린드롬의 여부에 따라,

요소가 짝수개인 팰린드롬은 최종적으로 길이가 2인 팰린드롬의 여부에 따라 결정되기 때문에 다음과 같이 나누었다. 

 

입력을 받을 때 길이가 1, 2인 펠림드롬을 확인하고,

for (int i = 1; i <= N; i++){
    scanf("%d", &arr[i]);
    dp[i][i] = 1;
    if (i > 1 && arr[i] == arr[i-1]) dp[i-1][i] = 1;
}

입력이 끝난 후 길이가 3 이상인 팰린드롬을 구했다.

for (int len = 2; len < N; len++)
    for (int S = 1; (E = S+len) <= N; S++)
        if (arr[S] == arr[E] && dp[S+1][E-1]) dp[S][E] = 1;

---

소스코드

#include <stdio.h>
int dp[2001][2001];
int main(){
    int N, M;
    scanf("%d", &N);
    int arr[N+1], S, E;
    for (int i = 1; i <= N; i++){
        scanf("%d", &arr[i]);
        dp[i][i] = 1;
        if (i > 1 && arr[i] == arr[i-1]) dp[i-1][i] = 1;
    }
	
    for (int len = 2; len < N; len++)
        for (int S = 1; (E = S+len) <= N; S++)
            if (arr[S] == arr[E] && dp[S+1][E-1]) dp[S][E] = 1;
		
    scanf("%d", &M);
    while (M--){
        scanf("%d %d", &S, &E);
        printf("%d\n", dp[S][E]);
    }
}

---

출처

10942번: 팰린드롬?