[백준] 10942 팰린드롬? - C++

 처음 문제를 접했을 때는 DP라는 생각이 들지 않고, 그냥 단순한 구현문제인 줄 알고 구현했더니 시간초과가 나왔다. 내가 짠 코드의 시간복잡도는 O(N * M) 이었다. (아래의 코드는 시간초과된 틀린 코드이다.)

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
int N, M;
int board[2005];

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> N;
    for (int i = 1; i <= N; i++) {
        cin >> board[i];
    }
    cin >> M;
    int S, E;
    while (M--) {
        cin >> S >> E;
        if (S == E) {
            cout << 1 << '\n';
            continue;
        }
        bool isPal = true;
        while (S < E) {
            if (board[S] != board[E]) {
                isPal = false;
                break;
            }
            S++; E--;
        }
        if (isPal) cout << 1 << '\n';
        else cout << 0 << '\n';
    }
}

 

 여기서 더 단축시키려면 이분탐색? DP? 등을 생각해보다가 이분 탐색은 말도 안되고 DP가 적당하다고 생각했다. 어떻게 DP로 이 문제를 풀까? 

 우선 DP 배열의 요소가 무엇을 의미하는지와 점화식을 세워둘 필요가 있다. S 번째 수부터 E 번째 수까지 팰린드롬을 물어보는 질문 수(M)이 1,000,000 이하이기 때문에 질문 수를 받는 반복문 안에서 뭔가 작업을 하면 안될 것 같다는 생각이 들어서,

• DP[S][E] : "S 번째 수부터 E 번째 수까지는 팰린드롬인가? 맞으면 1, 아니면 0"

라고 DP 배열 요소의 의미를 정해뒀다. 하지만, DP 배열 요소들간의 연결관계는 찾을 수 없었다. 하지만 DP 배열을 채우고 질문(M)을 받는 질문 반복문 안에서 다른 코드 없이 DP[S][E] 를 출력해준다면, 이전의 코드보다는 시간복잡도가 O(N^2)로 개선될 것이다. (N은 1,000 이하이고, M은 1,000,000 이하로 범위가 2배 이상 차이남)

 그래서 작성한 코드이다. 시간초과나지 않고 통과하는 것을 확인할 수 있었다. 

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
int N, M;
int board[2005];
int DP[2005][2005];

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> N;
    for (int i = 1; i <= N; i++) {
        cin >> board[i];
    }

    for (int i = 1; i <= N; i++) {
        DP[i][i] = 1;
        if (board[i - 1] == board[i]) DP[i - 1][i] = 1;
    }

    for (int gap = 2; gap < N; gap++) {
        for (int i = 1; i <= N - gap; i++) {
            int S = i, E = i + gap;
            
            if (board[S] == board[E] && DP[S + 1][E - 1]) DP[S][E] = 1;
        }
    }

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