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

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

 

#include <iostream>
#include <vector>
using namespace std;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n, m;
    cin >> n;

    vector<int> a(n);
    vector<vector<bool>> dp(n, vector<bool>(n, 0));

    for (int i = 0; i < n; i++) {
        cin >> a[i];
        dp[i][i] = 1;
        if (i == 0) continue;
        if (a[i] == a[i - 1]) dp[i - 1][i] = 1;
    }

    for (int i = 0; i < n - 1; i++) {
        for (int j = 1; j + i < n - 1; j++) {
            if (dp[j][j + i] && a[j - 1] == a[j + i + 1]) dp[j - 1][j + i + 1] = 1;
        }
    }

    cin >> m;
    while (m--) {
        int s, e;
        cin >> s >> e;
        cout << dp[s - 1][e - 1] << '\n';
    }
}

질문의 개수가 엄청 많고 수열의 크기는 상대적으로 작은 걸 보고 바로 dp로 풀어야겠다고 생각이 들었다. 그래서 dp 배열을 다음과 같이 정의했다.

dp[i][j] : i번 인덱스부터 j번 인덱스까지의 수들이 팰린드롬이면 true, 아니면 false

1) 수가 1개이거나 2) 수가 2개이면서 그 두 수가 같으면, 팰린드롬이다. 그렇게 가장 작은 단위를 먼저 채우고 점점 키워가면서 dp 배열을 채웠다. (Bottom-Up) 어떤 수들이 팰린드롬이고 그 앞과 뒤에 있는 수가 같다면 앞뒤 수까지 포함한 것도 팰린드롬이라는 사실을 통해 다음과 같이 점화식을 세울 수 있다. 

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

(AC)