(C++) BOJ 백준 10942번 펠린드롬?

백준 10942번 펠린드롬? (C++)

---

---

문제 설명

• 주어진 수열에서 펠린드롬을 찾아내는 문제.
• a,b가 주어지면 a~b의 수열이 펠린드롬인지 판별해야함.

---

풀이

• 펠린드롬을 직접 판별하는 것은 매우 간단하지만, 질문을 1000000번 할 수 있기 때문에 최악의 경우 시간이 너무 오래걸릴 수 있다. 이 문제의 시간 제한은 0.1 초이기 때문에 DP를 생각해야한다.
• 길이가 1인 수열일 경우 항상 펠린드롬.
• 길이가 2인 수열일 경우 두 숫자가 같다면 펠린드롬.
• 길이가 3이상인 수열일 경우 양 끝의 숫자가 같고 그 사이의 수열이 펠린드롬일 경우 펠린드롬.
• 위 3가지 조건을 고려하여 DP로 해결하였다.

---

코드

ㅇㄹㅇㄹ

#include <iostream>
using namespace std;
#define FOR(i,N) for(int i=1; i<=N; i++)
int N,M;
int nums[2001];
int DP[2001][2001];
void dp() {
    FOR(i,N) DP[i][i] = 1;
    FOR(i,N-1) if(nums[i] == nums[i+1]) DP[i][i+1] = 1;
    for(int i=3; i<=N; i++) {
        for(int j=1; j+i-1<=N; j++) {
            if(nums[j]==nums[j+i-1] && DP[j+1][j+i-2]==1) {
                DP[j][j+i-1] = 1;
            }
        }
    }
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> N;
    FOR(i,N) {
        cin >> nums[i];
    }
    dp();
    cin >> M;
    FOR(i,M) {
        int s,e; cin >> s >> e;
        cout << DP[s][e] << '\n';
    }
    return 0;
}