[BOJ 10942] 팰린드롬?

문제

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

10942번: 팰린드롬?

 

---

풀이

DP를 사용합니다.

주어진 수열 \(A\)에 대하여 배열 \(dp\)를 다음과 같이 정의할 수 있습니다:

 

\(dp[i][j]:\) \(A_{i}\)부터 \(A_{j}\)까지가 팰린드롬인지 아닌지 여부. (팰린드롬이면 1, 팰린드롬이 아니면 0)

 

다음 수열을 보겠습니다.

 

1

2

1

3

1

2

1

 

여기서 첫 번째 수 부터 마지막 수까지는 팰린드롬입니다.

또한, 2번째부터 6번째까지, 3번째부터 5번째까지, 그리고 4번째 모두 팰린드롬입니다.

여기서 규칙을 찾아보면 \(i\)번째부터 \(j\)번째까지가 팰린드롬이면 \(i-1\)번째부터 \(j-1\)번째까지도 팰린드롬입니다.

그러므로 배열 \(dp\)에 다음 값을 넣으면 됩니다:

$$dp[i][j] = \begin{cases}
 1, &\text{if}\ dp[i+1][j-1] = 1 \ \text{and}\ A_{i} = A_{j}\\ 
 0, &\text{otherwise }
\end{cases}$$

\(dp[i+1][j-1]\)이 팰린드롬인지 아닌지 여부를 보고 남은 \(A_{i}\)와 \(A_{j}\)만 비교하면 답을 알 수 있습니다.

 

---

코드

#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;

typedef long long ll;
typedef pair<int, int> p;

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

    int N, M;
    cin >> N;
    vector<int> input(N);
    vector<vector<int>> dp(N, vector<int>(N, 0));
    for (int i = 0; i < N; ++i) cin >> input[i];

    for (int i = 0; i < N; ++i) dp[i][i] = 1;
    for (int i = 0; i < N - 1; ++i) dp[i][i + 1] = input[i] == input[i + 1];

    for (int len = 3; len <= N; ++len) {
        for (int i = 0; i < N - len + 1; ++i) {
            int j = i + len - 1;
            dp[i][j] = input[i] == input[j] && dp[i + 1][j - 1];
        }
    }

    cin >> M;
    while (M--) {
        int a, b;
        cin >> a >> b;
        a--; b--;
        cout << dp[a][b] << "\n";
    }

    return 0;
}