[BOJ 10942] 팰린드롬?

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

10942번: 팰린드롬?

 

 

 

다이나믹 프로그래밍의 단골 소재인 팰린드롬이다.

 

 

 

 

다이나믹 프로그래밍의 핵심은, 큰 문제들을 해결하기 위해서 작은 문제들의 값을 이용하는 것이 핵심이다.

 

 

 

---

 

 

 

그렇다면,  팰린드롬을 분석해보자.

 

 

 

 

인덱스 i ~ j의 숫자들이 팰린드롬인지 확인해야 한다.

 

 

 

 

다이나믹 프로그래밍의 본질, 큰 문제를 해결하기 위해서 작은 문제들의 값을 이용해보자.

 

 

 

 

DP[i][j]를 인덱스 i부터 j까지 펠린드롬 여부라고 정한다.

 

 

 

 

DP[i][j]를 큰 문제라고 했을 때, 작은 문제는 DP[i + 1][ j - 1]이 될 것이다.

 

 

 

 

DP[i + 1][j - 1] 펠린드롬이고, 인덱스 i의 값과 인덱스 j의 값이 같다면, 펠린드롬이 될 것이고, 그렇지 않으면 펠린드롬이 아니다.

 

 

 

이걸 식으로 표현해보면,

 

 

 

 

DP[i][j] = 1 (if, DP[i + 1][j - 1] && arr[i] == arr[j])

 

 

 

 

DP[i + 1][j - 1]이 0이라면, 절대로 펠린드롬이 될 수 없다. 

 

 

 

 

따라서, 위의 식을 다이나믹 프로그래밍으로 작성하면 된다.

 

 

 

 

가장 길이가 짧은 펠린드롬부터, 가장 길이가 긴 펠린드롬을 이중 for문으로 구해줄 것이다.

 

 

 

 

코드(C++).

 

#include <iostream>

#include <algorithm>

 

using namespace std;

 

int N, M;

int arr[2001];

int dp[2001][2001];

 

int main(void) {

    cin >> N;

    for (int i = 1; i <= N; i++) {

        cin >> arr[i];

        dp[i][i] = 1;

    }

 

    for (int j = 1; j <= N - 1; j++) {

        dp[j][j + 1] = (arr[j] == arr[j + 1]) ? 1 : 0;

    }

    

    for (int i = 2; i <= N - 1; i++){

        for(int j = 1; j <= N - i; j++){

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

                dp[j][j + i] = 1;

        }

    }

    

    cin >> M;

    for (int i = 1; i <= M; i++) {

        int S, E;

        scanf("%d %d", &S, &E);

        printf("%d\n", dp[S][E]);

    }

 

    return 0;

}