[BOJ] 백준 10942 팰린드롬?

문제 링크

www.acmicpc.net/problem/10942

10942번: 팰린드롬?

풀이

문자열 $s$의 양 끝이 같고, 그 사이 문자열이 팰린드롬이면 $s$도 팰린드롬입니다.

기저값으로 문자열 길이가 1이면 항상 팰린드롬, 길이가 2일땐 두 문자가 같으면 팰린드롬입니다.

 

$d[i][j]$: 문자열 $s[i]$ ~ $s[j]$가 팰린드롬이면 1, 아니면 0

$d[i][j] = (s[i] == s[j])$ && $(d[i+1][j-1])$

 

길이가 작은 값부터 채워나가면 됩니다.

 

정답 코드

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

int n, m;
int p[2222], d[2222][2222];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i < n + 1; i++) {
        cin >> p[i];
    }
    for (int k = 0; k < n; k++) {
        for (int i = 1, j = k + 1; j < n + 1; i++, j++) {
            if (k == 0) d[i][j] = 1;
            else if (k == 1) d[i][j] = p[i] == p[j];
            else d[i][j] = p[i] == p[j] && d[i + 1][j - 1];
        }
    }
    cin >> m;
    while (m--) {
        int s, e;
        cin >> s >> e;
        cout << d[s][e] << '\n';
    }
}