[백준] 10942 - 팰린드롬?

1. 문제 이해

수열과, 그 수열 내에서 특정 범위가 주어진다. 주어진 특정 범위의 수열이 팰린드롬인지 아닌지 확인하는 문제이다.

---

2. 문제 풀이

주어지는 범위는 왼쪽과 오른쪽 인덱스 총 2개이다. 이 인덱스를 이용해 DP 배열을 만든다.

팰린드롬인 범위가 있다면, 왼쪽 인덱스 + 1. 오른쪽 인덱스 -1 한 범위도 팰린드롬이 된다.

만약 팰린드롬이 아니라면, 그 안쪽 범위는 팰린드롬 일 수 있다.

 

즉, 범위가 주어진다면, 왼쪽 인덱스 + 1. 오른쪽 인덱스 -1 했을 때의 팰린드롬 결과가 결국 정답이 된다..

 

DP를 만드는 시간복잡도는 2000 * 2000 ( 왼쪽 인덱스 가능한 값, 오른쪽 인덱스 가능한 값 ) 이 되어 0.5 초 이내에 수행이 된다.

 

예를 들어. 수열이 1 2 3 4 5 4 3 2 1이고 왼쪽 인덱스가 1 오른쪽 인덱스가 7이라고 하자

 

• 왼쪽 인덱스 1 이고 오른쪽 인덱스가 7 이면 2 == 2 이므로 인덱스를 각각 +1. -1 해서 비교하자
• 왼쪽 인덱스 2 이고 오른쪽 인덱스가 6 이면 3 == 3 이므로 인덱스를 각각 +1. -1 해서 비교하자
• 왼쪽 인덱스 3 이고 오른쪽 인덱스가 5 이면 4 == 4 이므로 인덱스를 각각 +1. -1 해서 비교하자
• 왼쪽 인덱스 4 이고 오른쪽 인덱스가 4 이면 5 == 5 이므로 인덱스를 각각 +1. -1 해서 비교하자
• 왼쪽 인덱스 5 이고 오른쪽 인덱스가 4 이면, 팰린드롬임이 확인된다.

만약 위의 과정에서 Equal이 성립하지 않는다면 바로 중단시킨다. 그러므로, 왼쪽 인덱스가 오른쪽 인덱스보다 커진다면 팰린드롬이 확정된다.

 

그러므로 만약 왼쪽 인덱스가 0 오른쪽 인덱스가 8이라고 하면 왼쪽 인덱스가 1이고 오른쪽 인덱스가 7일때의 결과를 이용한다.

 

---

3. 제출 결과

---

4. 문제 코드

#include <bits/stdc++.h>
using namespace std;
int cache[2001][2001];
int num[2001];
int N;
int palin(int s, int e) {
    if ( s > e) { return 1;}
    int &ret = cache[s][e];
    if(ret != -1) { return ret; }
    if(num[s] != num[e]) { return ret = 0;}
    return ret = palin(s+1, e-1);
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    memset(cache, -1, sizeof(cache));
    cin >> N;
    for(int i=1; i<=N; i++) {
        cin >> num[i];
    }
    int m, s,e;
    cin >> m;
    for(int i=0; i<m; i++) {
        cin >> s >> e;
        cout << palin(s,e) << "\n";
    }   
}