[BOJ] 10942

팰린드롬?

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

분류

• Gold 3

• 다이나믹 프로그래밍

해법

다이나믹 프로그래밍 문제였습니다.

bottom-up으로 접근하면 됩니다.

두 개의 ?칸 사이가 palindrome이라면 ?칸 안에 있는 숫자 두 개가 같으면 전체가 palindrome임을 이용했습니다.

정답 코드

/*
BOJ 10942: 팰린드롬?
*/

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

int n, m;
int arr[2005];
int dp[2005][2005];

void sol() {
    for (int i = 0; i < n; i++) {
        dp[i][i] = 1;
    }
    for (int l = 2; l <= n; l++) {
        for (int st = 0; st < n - l + 1; st++) {
            int en = st + l - 1;
            if (arr[st] != arr[en]) continue;
            dp[st][en] = l == 2 || dp[st + 1][en - 1];
        }
    }
}

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    sol();
    cin >> m;
    while (m--) {
        int st, en;
        cin >> st >> en;
        cout << dp[st - 1][en - 1] << "\n";
    }
    return 0;
}