[C++] 백준/Gold/10942. 팰린드롬?

문제: 팰린드롬? (백준 10942번)

문제 분석

입력으로 주어진 단어(숫자 배열)의 구간에 대해, 해당 구간이 팰린드롬인지 판별하는 문제다.
n개의 수가 주어지고, m개의 질의가 주어진다. 각 질의는 시작 인덱스 S와 끝 인덱스 E가 주어지며, 이 구간이 팰린드롬이면 1, 아니면 0을 출력한다.

---

동적 계획법(DP)을 이용해, 구간 $[i, j]$가 팰린드롬인지 판별하는 2차원 배열 dp를 구성한다.

 

기저 조건:

• 한 글자짜리 구간은 항상 팰린드롬이므로, $dp[i][i] = true$
• 인접한 두 수가 같으면, $dp[i][i+1] = true$

 

점화식:

$dp[i][j] = \text{true} \quad \text{if} \quad v[i] = v[j] \quad \text{and} \quad dp[i+1][j-1] = \text{true}$

 

이후 m개의 질의를 입력받아, dp[S][E]의 값을 출력한다.

 

전체 코드

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

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

    int n, m;
    cin >> n;
    vector<int> v(n + 1);
    vector<vector<bool>> dp(n + 1, vector<bool>(n + 1, false));

    for (int i = 1; i <= n; i++) {
        cin >> v[i];
        dp[i][i] = true; 
    }

    for (int i = 1; i < n; i++) {
        if (v[i] == v[i + 1]) dp[i][i + 1] = true;
    }

    for (int len = 2; len <= n; len++) {
        for (int i = 1; i + len <= n; i++) {
            int j = i + len;
            if (v[i] == v[j] && dp[i + 1][j - 1]) {
                dp[i][j] = true;
            }
        }
    }

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