백준 10942 팰린드롬? (C++)

10942번: 팰린드롬?

dp를 이용한 문제이다. 기존 팰린드롬을 확인하는 방식으로 알고리즘을 짜게 되면 시간 초과가 난다. 팰린드롬은 좌우가 대칭이 되는 구조를 말한다. 즉 n[s] == n[e]라면 n[s+1] == n[e-1]이 무조건 성립이 되어야 한다. 이를 이용하여 dp를 사용하였다. 먼저 시작과 끝이 같은 인덱스인 경우는 true로 초기화를 해주고 n[s+1] == n[e-1] 구조를 사용하기 위해 연속으로 같은 두 숫자가 나올 경우도 true로 초기화 해준다. 그리고 dp를 사용하기위해 반복문을 거꾸로 돌면서 팰린드롬을 찾아 true로 저장해주고 질문에 따라 답을 출력해주었다. 생각보다 시간이 오래 걸린 문제였다. dp 문제를 더 많이 풀어봐야 겠다.

#include <iostream>
#include <vector>
#include <string>

using namespace std;

int N, M;
int n[2001];
vector<pair<int, int>> v;
bool dp[2001][2001];

void solution() {
    for (int i = 1; i <= N; i++) {
        dp[i][i] = true;
    }

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

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

    for (int i = 0; i < v.size(); i++) {
        int S = v[i].first;
        int E = v[i].second;

        cout << dp[S][E] << "\n";
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> N;

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

    cin >> M;

    int S, E;
    for (int i = 0; i < M; i++) {
        cin >> S >> E;
        v.push_back({ S,E });
    }

    solution();

    return 0;
}