[10942] 팰린드롬? - C++

---

문제

 

모든 경우의 수를 확인하는 브루트 포스로 푸는 것은 불가능해 보인다.

N은 최대 2000개 이고, 질문의 개수가 최대 1,000,000개 

 

[ 1, 2000 ]이라는 질문이 1,000,000개 나온다면 20억 번 연산을 해야 하므로 0.5초 안에는 절대 불가능

 

Q. DP로는 가능 할까?

A. 가능하다.

점화식

명령 : [ 1, 7 ]이 팰린드롬이지 확인하고 싶다면

[ 2, 6 ] 이 팰린드롬 인지 확인 하고 [ 1 ] == [ 7 ]이 같은 지 확인해 주면 된다.

그런데 또 [ 2, 6 ]이 팰린드롬인지 알려면 [ 3, 5 ]를 알아야 하므로

DP로 풀 수 있다.

테이블 정의

DP [ i ][ j ] = i번째부터 j번째 까지가 팰린드롬 인지 확인 Boolean Type

입력받기

for(int i = 1; i <= n; ++i){
    dp[i][i] = 1;
    cin >> arr[i];
  }

부분 코드

  for(int i = n; i > 0; --i){
    for(int j = i+1; j <= n; ++j){
      if(j == i+1 && arr[i] == arr[j])
        dp[i][j] = 1;
      else if(arr[i] == arr[j] && dp[i+1][j-1])
        dp[i][j] = 1;
    }
  }

 

if(j == i+1 && arr[i] == arr[j])
        dp[i][j] = 1;

이 부분이 의아할 수 있을 것 같다.

첫 번째 j에서 실행되는 로직인데, 이 로직이 없다면 아래 로직이 실행될 것이다.

else if(arr[i] == arr[j] && dp[i+1][j-1])
        dp[i][j] = 1;

만약 i = 2, j = 3이라고 가정해 보자

 

dp [ 2+1 ][ 2-1 ]

dp [ 3 ][ 1 ]은 말이 되지 않기 때문에 첫 번째 실행 로직을 넣어준 것이다.

---

전체 코드

#include <bits/stdc++.h>

using namespace std;
void init(){
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
}

int n, s, e;
int arr[2003];
bool dp[2002][2002];

int main(){
  init();
  cin >> n;
  for(int i = 1; i <= n; ++i){
    dp[i][i] = 1;
    cin >> arr[i];
  }

  for(int i = n; i > 0; --i){
    for(int j = i+1; j <= n; ++j){
      if(j == i+1 && arr[i] == arr[j])
        dp[i][j] = 1;
      else if(arr[i] == arr[j] && dp[i+1][j-1])
        dp[i][j] = 1;
    }
  }
  
  int t;
  cin >> t;
  while(t--){
    int a, b;
    cin >> a >> b;
    cout << (dp[a][b] ? 1 : 0) << '\n';
  }

  return 0;
}

 

긴 글 읽어 주셔서 감사합니다.