[백준 10942번] 팰린드롬? (C++)

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

10942번: 팰린드롬?

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int arr[2001];
int dp[2001][2001];

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);
    
    int N, M;
    cin >> N;
    for(int i=1; i<=N; i++)
    {
        cin >> arr[i];
        dp[i][i]=1; //1글자인 경우
        if(arr[i-1]==arr[i] && i>1) dp[i-1][i]=1; //2글자인 경우(11, 22 등)
    }


    for(int i=N-2; i>=1; i--) //3글자 이상인 경우
    {
        for(int j=i+2; j<=N; j++) 
        {
            if(arr[i]==arr[j] && dp[i+1][j-1]) dp[i][j]=1;
        }
    }

    cin >> M;
    while(M--)
    {
        int S, E;
        cin >> S >> E;
        cout << dp[S][E] <<"\n";
    }

    return 0;
}

dp의 응용문제이다.

먼저 고려해야할 경우의 수는 다음과 같이 3가지다.

<1글자>
dp[i][i]의 경우는 무조건 팰린드롬 수

<2글자>
연속해서 같은 경우는 팰린드롬 수 (11, 22와 같은 경우)

<3글자 이상>
각 위치 (i, j)의 값이 같은지와, (i+1, j-1)의 값이 펠린드롬수인지 확인 
해당 값이 펠린드롬 수라면 dp[i][j]도 펠린드롬 수
ex) 1 2 1 
2 -> dp[2][2]이므로 펠린드롬 수
i = 1, j = 3 -> dp[2][2]가 펠린드롬 수이고 arr[i]와 arr[j]의 값이 같으므로 dp[1][3]도 펠린드롬 수

3글자 이상인 경우가 다소 까다롭다.

2중 반복문을 통하여 구하였는데, i를 1부터 시작하면 다음과 같은 문제가 생긴다.

i=1, j=3인 경우 : dp[2][2]의 값을 알고 있으므로 현재 값도 판별가능 (가운데가 1글자)
i=1, j=4인 경우 : dp[2][3]의 값을 알고 있으므로 현재 값도 판별가능 (가운데가 2글자)
i=1, j=5인 경우 : dp[2][4]의 값을 모르므로 현재 값 판별 불가능 (가운데가 3글자)

이렇듯 가운데가 1~2글자 인 경우에는 사전에 1~2글자에 대해 팰린드롬 수 인지 판별하였으므로 현재 위치에 대해 팰린드롬 수인지 판별이 가능하지만, 가운데가 3글자 이상이면 해당 범위의 값이 팰린드롬 수인지 알 수가 없다.

 

따라서 i를 1부터 시작하는 것이 아닌 맨 뒤라고 할 수 있는 N-2부터 시작한다.

i=N-2부터 시작하고, j은 i+2부터 시작하므로 첫 탐색은 마지막 3자리에 대해 하게 된다.

이후에 계산하다보면 i=3, j=7과 같이 가운데가 3글자인 경우가 나온다.

하지만 i를 큰 값부터 시작하여 i--;로 탐색했기에 i-1, j+1에 해당하는 i=4, j=6의 값을 i=4일 때 이미 판별을 해놓은 상태이다.

따라서 i를 큰 값(뒤)부터 탐색한다면 이렇게 문제없이 이어서 판별해나갈 수 있다.