[cpp 알고리즘] 백준 10942 팰린드롬?

[백준] 10942 팰린드롬? cpp 풀이

DP, 다이나믹 프로그래밍

 

문제 출처: https://www.acmicpc.net/problem/10942

10942번: 팰린드롬?

문제 요약

- 자연수 N개(1<=N<=2,000)가 주어지고, 총 M번(1<=M<=1,000,000)의 테스트케이스에서 S번째 수부터 E번째 수가 팰린드롬인지 확인하는 문제이다. 각각의 테스트케이스에 대해 팰린드롬이면 1을, 아니면 0을 출력하면 된다. 

- 팰린드롬 : 양쪽이 대칭이 되는 문자열 ex) a, aa, abcba

풀이 정리

1. 가장 먼저 생각했던 건, panlidrome 여부를 체크하는 panlidrome(int s, int e)함수를 만들어서 for문으로 팰린드롬 여부를 검사하고, 매번 0 혹은 1을 리턴하는 것을 생각했다. 하지만 시간제한이 0.5초였다. 

 

2. dp배열 메모이제이션을 사용했다. 

dp[s][e]: s에서 e구간까지 팰린드롬 수이면 1을, 아니면 0을 기록한다 .

 

(1) 길이가 1일 경우, dp[i][i]는 팰린드롬이다.

(2) 길이가 2일 경우, arr[i] == arr[i+1]라면 팰린드롬이다. 

(3) 길이가 3 이상일 경우, arr[i] == arr[j] 이고, dp[i+1][j-1] == 1이라면 팰린드롬이다. 

      ex) 만약 s=2, e=6이 주어진 경우,

            arr[2] == arr[6] 이고, dp[3][5] == 1이라면(=arr 배열의 3~5사이 수가 팰린드롬이다) 

            arr 배열의 2~6사이의 수도 팰린드롬일 것이고, dp[2][6] == 1이라고 표현할 수 있다. 

C++ 코드

#include <iostream>
using namespace std;

int N,M;
int arr[2010];
int dp[2010][2010];

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    cin >> N ;
    for(int i=1; i<=N; i++) cin >> arr[i];
    cin >> M;
    
    for(int i=1; i<=N; i++){
        dp[i][i]=1; //한자리 수는 팰린드롬
        if(i!=1 && arr[i-1] == arr[i]) dp[i-1][i]=1; //두자리수가 같은 경우 팰린드롬
    }
    
    for(int i=2; i<=N-1; i++){
        for(int j=1; i+j<=N; j++){
            if(arr[j]==arr[i+j] && dp[j+1][i+j-1]==1)
                dp[j][i+j]=1;
        }
    }
    
    while(M>0){
        int s,e; cin >> s >> e;
        
        if(dp[s][e] == 1) cout << 1 << "\n";
        else cout << 0 << "\n";
        
        M--;
    }
    
    return 0;
}

 

*메모이제이션(memoization):  컴퓨터 프로그램이 동일한 계산을 반복해야 할 때, 이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 하는 기술