[백준 10942번] 팰린드롬 |오토마타|,|DP연습|

백준 10942번

10942번: 팰린드롬?

입력
1.N(문자열 길이)
2. M(질문의 개수)
3. S, E(S번째부터 E번째 까지의 부분 수열 인덱스)

---

출력
1.입력된 S E 의 인덱스를 보고 수열 S->E 까지의 문자열이 팰린드롬이라면
1 출력,,, 아니면 0 출력

---

생각방법
   DP문제다.   점화식을 고민하자

오토마타 -> 팰린드롬PDF 9패이지 참조

제 10 장 오토마타 , 문법 , 언어

여기서 중요한점은

   1.DP[i][i] 은 모두 팰린드롬이다.

 

   2.길이가 2인 | arr[i]와 arr[i+1] (단,i +1 <= N) |을 포함하는 부분문자열 이 같다면, 그것 또한 모두 팰린드롬 일것이다.

 

   3.제일 중요한것! DP 만들기 길이가 3이상인 부분문자열 확인할것이다.
      left 인덱스 "L" right 인덱스 "R" 가 있다고 하자 (단, 1 <= L < R <= N)
      > arr[L] == arr[R] 이면서~(위의 펠린드롬 정의의 (2)을 참고할때 arr[L] , arr[R] 는 'a'가 될 부분이다.)
      > DP[L+1][R-1] (위의 펠린드로 정의의 (3)을 참고할때 DP[L+1][R-1]는 'x'가 될 부분이다.)

 

      DP[L+1][R-1] 이 펠린드롬이라면 DP[L][R] 또한 펠린드롬일것이다.

 

사용하는 자료구조
2차원 배열!
>DP 배열

1차원 배열
>arr 자료담기

---

https://colorscripter.com/

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

#include <iostream> using namespace std;   int dp[2020][2020]; int arr[2020];   int main() {     ios::sync_with_stdio(0); cin.tie(0);       //---------------------------     int N; cin >> N;     for (int i = 1; i <= N; i++)         cin >> arr[i];     //---------------------------     for (int i = 1; i <= N; i++)     {         dp[i][i] = 1;         if (i+1 <= N && arr[i] == arr[i + 1]) {             dp[i][i + 1] = 1;             dp[i+1][i] = 1;         }     }       for (int i = 1; i <= N; i++){         for (int j = 1; j <= N; j++){             int l = i, r= j;             if (i > r)               if (1 <= r-1 && l+1 <= N) {                 if (arr[l] == arr[r] && dp[l + 1][r - 1] == 1) {                     dp[l][r] = 1;                     dp[r][l] = 1;                 }             }         }     }       //---------------------------     int M; cin >> M;     for (int i = 1; i <= M; i++)     { int S, E; cin >> S >> E;cout << dp[S][E] << '\n';}     //---------------------------     return 0; } Colored by Color Scripter

cs