[C/C++] 백준 10942: 팰린드롬? (DP)

 

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

10942번: 팰린드롬?

 

풀이?

 먼저 펠린드롬이란 거꾸로 읽어도 제대로 읽는 것과 같은 문장을 뜻한다. 이 문제에서는 각 질문에 대하여 팰린드롬인지 아닌지를 답해야 하는데 질문의 개수가 10^6이고 수열의 크기가 최대 2000이기 때문에 사실상 각 질문마다 팰린드롬인지 확인을 한다면 시간복잡도가 O(NM)이 되기 떄문에 시간안에 풀 수 없다. 그렇기 때문에 각 수가 팰린드롬인지 아닌지를 새로운 배열에 저장해가며 풀어야만 시간 내의 해결이 가능하다.

 

 다만 각 질문을 해결해가며 팰린드롬인지 아닌지를 저장해도 질문이 중복되지 않으면 저장을 한 기존의 방식대로 할 경우 저장을 안한 것과 마찬가지가 된다. 이때 생각해야하는 아이디어가 있다.

 

 바로 팰린드롬 수는 양쪽 (맨 처음 수와 맨 마지막 수)를 뺸 나머지 수 역시도 팰린드롬 수가 된다는 것이다. 즉, 길이가 n인 팰린드롬 수가 있고 맨 처음 수의 위치를 left, 맨 마지막 수의 위치를 right라고 하면 (right-left+1==n) n/2만큼 for문을 돌며 팰린드롬이란 것을 check[][] 배열에 저장해두면 된다. 이렇게 될 경우, 다음 번에 check[][]==1 이라면 바로 팰린드롬 수인 것을 알 수 있게 되어 팰린드롬 수를 찾는 시간을 획기적으로 줄일 수 있다. 코드는 아래와 같다

int calculate_P(int left,int right){
  int n=(right-left+1)/2; //연산 횟수
  int tmp1=left, tmp2=right;
  for(int i=1;i<=n;i++){
    if(arr[tmp1]!=arr[tmp2]){ //펠림드롬이 아닐 때
      check[left][right]=2;
      return 0;
    }
    tmp1++,tmp2--;
  }

  for(int i=1;i<=n;i++){ //left부터 right까지 팰린드롬이면 left+1, right-1까지도 팰린드롬
    check[left][right]=1;
    left++,right--;
  }  

  return 1;
}

 

소스코드

#include <iostream>
#include <algorithm>
#include<bits/stdc++.h>
#include<queue>
#include<map>

using namespace std; //모든 식별자가 고유하도록 보장하는 코드 영역
int arr[2001];
int check[2001][2001];

int calculate_P(int left,int right){
  int n=(right-left+1)/2; //연산 횟수
  int tmp1=left, tmp2=right;
  for(int i=1;i<=n;i++){
    if(arr[tmp1]!=arr[tmp2]){ //펠림드롬이 아닐 때
      check[left][right]=2;
      return 0;
    }
    tmp1++,tmp2--;
  }
  for(int i=1;i<=n;i++){ //left부터 right까지 팰린드롬이면 left+1, right-1까지도 팰린드롬
    check[left][right]=1;
    left++,right--;
  }  
  return 1;
}

int main() {    
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n,m;
  cin>>n;
  for(int i=1;i<=n;i++){
    cin>>arr[i];
  }
  cin>>m;
  for(int i=1;i<=m;i++ ){
    int tmp1,tmp2;
    cin>>tmp1>>tmp2;
    int decision=check[tmp1][tmp2];
    if(decision==0){ //모를때
      int result=calculate_P(tmp1,tmp2);
      cout<<result<<"\n";
    }
    else if(decision==1)
      cout<<1<<"\n";
    else
      cout<<0<<"\n";
  }    
}