[백준][C++] 10942번: 팰린드롬? <212>

직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다.

 

10942번: 팰린드롬?

생각의 흐름

생각보다 간단한 DP 문제이다.

 

1) 길이가 1인 경우

모두 팰린드롬 수가 된다.

 

2) 길이가 2인 경우

바로 다음 칸의 수와 비교해서 같은지 확인하면 된다.

 

3) 길이가 3 이상인 경우

우리의 배열 input이 다음과 같다 해보자.

1 2 1 3 1 2 1

이중 가장 중간에 있는 P : [1, 2, 1] 은 팰린드롬 수 이다. 앞으로 읽으나, 뒤로 읽으나 같은 수가 나오기 때문이다.

이 팰린드롬 수를 P 라고 하면  2 p 2 또한 팰린드롬 수가 된다.

따라서 DP[i][j] = DP[i+1][j-1]이 될 것 이다.

 

나의 코드

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

int N, M;
int arr[MAX];
int DP[MAX][MAX];
vector<pair<int, int>> vec;

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

    cin >> N;
    for(int i = 1; i <= N; i++) {
        cin >> arr[i];
    }

    cin >> M;
    for(int i = 0; i < M; i++){
        int from, to;
        cin >> from >> to;
        vec.push_back({from, to});
    }

    for(int i = 1; i <= N; i++) {
        DP[i][i] = 1; // 길이가 1인 경우
    }

    for(int i = 1; i < N; i++) {
        if(arr[i] == arr[i+1]){
            DP[i][i+1] = 1; // 길이가 2인 경우
        }
    }

    for(int i = 2; i < N; i++) { // 차이 나는 칸의 수
        for(int j = 1; j <= N-i; j++) {
            if(arr[j] == arr[j+i] && DP[j+1][j+i-1]) {
                DP[j][j+i] = 1;
            }
        }
    }

    for(int i = 0; i < M; i++) {
        cout << DP[vec[i].first][vec[i].second] << "\n";
    }

    return 0;
}