백준 10942 팰린드롬? 쉬운 풀이 (C++/CPP)

문제링크 : https://www.acmicpc.net/problem/10942

아이디어

• 팰린드롬 개념

  • 팰린드롬 : 앞에서 읽으나 뒤에서 읽으나 같은 단어
  • 문자열에서 접두사와 접미사가 겹치는 부분이 발생(이때 홀수로 겹쳐서 대칭되어야함)
  • 구하는 방법 :
    • KMP
      • 접두사와 접미사가 같은 길이(f[s.size()-1])에서 반복하는 문자열(s.size()-f[s.size()-1])으로 나누어 떨어지지 않을때
      • f[s.size()-1] % (s,size() - f[s.size()-1])
    • DP
      • DP[st][en] : st부터 시작해서 en까지 끝날때 팰린드롬 true, false
      • DP[st][en] = true일때, 각각 앞뒤 문자열이 같을경우(arr[st-1] == arr[en+1]) dp[st-1][en+1] = true
  • KMP 사용할 경우
    • 1부터 계산하는건 문제가 안됨
    • 중간부터 계산하는 건 어떻게 진행?
    • 매번 KMP를 다시구할경우
      • O(M * N) = 2e9 > 시간초과
    • KMP 사용해서는 불가
  • DP 사용할 경우
    • 숫자들에 대해 미리 DP를 구해놓고
    • 각각의 요청에 따라 DP 값 출력

시간복잡도 계산

• DP 구하기 : O(N^2)
• 요청에라 확인 : O(M)
• 합 : O(N^2+M) : 4e6 + 1e6

인트 계산

• 입력 숫자값 최대 1e5
  • DP 값 : true, false

코드

#include <iostream>
 
using namespace std;
 
int arr[2010];
int dp[2010][2010];
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int N; cin >> N;
    for(int i=0; i<N; i++) cin >>arr[i];
    
    fill(&dp[0][0], &dp[2009][2010], 0);
    
    // 길이 1일때
    for(int i=0; i<N; i++) dp[i][i] = 1;
    
    // 길이 2일때
    for(int i=0; i<N-1; i++) if(arr[i] == arr[i+1]) dp[i][i+1] = 1;
    
    // 길이 3이상
    // 각 길이 케이스에서
    for(int l=2; l<N; l++) {
        // 시작하는 곳
        for(int i=0; i<N-l; i++) {
            if(arr[i] == arr[i+l] && dp[i+1][i+l-1]) dp[i][i+l] = 1;
        }
    }
    
    int M; cin >> M;
    for(int i=0; i<M; i++) {
        int j,k; cin >> j >> k;
        cout << dp[j-1][k-1] << '\n';
    }
    
    return 0;
}
 

문제유형

• DP - 팰린드롬
  • 팰린드롬 : 앞에서 읽으나 뒤에서 읽으나 같은 단어
  • DP[st][en] : st부터 시작해서 en까지 끝날때 팰린드롬 true, false
  • DP[st][en] = true일때, 각각 앞뒤 문자열이 같을경우 팰린드롬
  • 문자길이 1,2, 3이상일때 각각 나눠서 수행