[10942번] 팰린드롬?

문제 출처 :

https://www.acmicpc.net/problem/10942

알고리즘 분석 :

문제 해결에 필요한 사항

1. Dynamic Programming

2. 점화식 세우는 방법

DP를 이용해서 해결하는 문제이다.

8달 전 이문제를 처음 접했을 때는 쿼리에 대한 개념이 없었고, 시간 복잡도를 어떻게 구성할 지 몰라 시간 초과를 받은 적이 있다.

이 문제는 쿼리의 양이 100만개이고 수열의 크기가 2000이기에 자칫하면 2,000*1,000,000 만큼의 반복이 돌 수 있다.

따라서 DP를 이용해야 하고 DP는 다음과 같은 점화식을 이용한다.

DP[i][j] :: i~j가 팰린드롬인가?

1. DP[i][i]는 무조건 팰린드롬이다.(자기자신)

2. arr[i] == arr[i+1]이면 DP[i][i+1]은 팰린드롬이다. (aa, bb같은 경우)

3. i에서 0번째(자기자신), i에서 1번째(자신 바로 다음 값)의 DP를 모두 구했으니 이제 i에서 k번째가 팰린드롬인지 확인한다.

k라는 값은 2부터 시작할 것이고 n - 1까지 있을 것이다. (i가 1일때 n -1번째가 가장 긴 팰린드롬 검사 값이다.)

아래 소스 코드를 통해 확인해보자.

i는 n-k번째 까지인데 이 이유는 팰린드롬은 반틈만 확인하면 되기 때문이다.

그리고 j의 의미는 i번째와 i + k번째가 같은 값인지 확인하는 변수이다.

DP[i][j] = true라면 i~j의 문자는 팰린드롬이라는 의미이다.

소스 코드 : 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52

#include <iostream> #include <cstdio>   using namespace std;   int arr[2002]; bool DP[2002][2002];   int main() {     int n;       scanf("%d", &n);       for (int i = 1; i <= n; i++)         scanf("%d", &arr[i]);       for (int i = 1; i <= n; i++)         DP[i][i] = true;       for (int i = 1; i <= n-1; i++)         if (arr[i] == arr[i + 1])             DP[i][i + 1] = true;       // k 번째     for (int k = 2; k <= n-1; k++)     {         // i부터 ~ n - k 번째 까지         for (int i = 1; i <= n - k; i++)         {             int j = i + k;             if (arr[i] == arr[j] && DP[i + 1][j - 1])                 DP[i][j] = true;         }     }       int m;     scanf("%d", &m);       while (m--)     {         int start, end;         scanf("%d %d", &start, &end);           DP[start][end] ? printf("1\n") : printf("0\n");       }     return 0; }   //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocus