[BOJ] 10942 : 팰린드롬?

문제 링크

10942번: 팰린드롬? (acmicpc.net)

10942번: 팰린드롬?

풀이

팰린드롬이란 양쪽이 대칭을 이루는 것을 말한다. 예를 들면 12321 같은 것들.

최대 2000길이의 수열을 1000000회 동안 매번 팰린드롬인지 검사하면 0.5초의 시간으로 절대 부족하다.

그래서 palinedrome이라는 이차원 배열을 만들어 palinedrome[Start][End] 까지가 팰린드롬인지 아닌지 저장해뒀다.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <string.h>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <climits>
#include <algorithm>
#include <tuple>
#include <cmath>
using namespace std;
typedef long long ll;
const int MAX_N = 2000 + 5;
int N, M;
int S, E;
vector<int> arr;
int palinedrome[MAX_N][MAX_N];
 
bool Check(int St, int Ed) {
    for (int i = 0; i <= (E - S) / 2; i++) {
        if (palinedrome[St + i][Ed - i] == 1)
            return true;
        if (palinedrome[St + i][Ed - i] == 2)
            return false;
        else {
            if (arr[St + i] != arr[Ed - i]) {
                palinedrome[St + i][Ed - i] = 2;
                return false;
            }
        }
    }
    for (int i = 0; i < (E - S) / 2; i++) {
        palinedrome[St + i][Ed - i] = 1;
    }
    return true;
}
 
int main(void)
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> N;
    int num;
    arr.push_back(0);
    for (int i = 0; i < N; i++) {
        cin >> num;
        arr.push_back(num);
    }
    cin >> M;
    while (M--) {
        cin >> S >> E;
        if (S == E) {
            cout << "1\n";
            continue;
        }
        bool chk = Check(S, E);
        if (chk) cout << "1\n";
        else {
            palinedrome[S][E] = 2;
            cout << "0\n";
        }
    }
    return 0;
}
 
 

수열 양쪽에서 부터 검사하다가 중간 부분이 팰린드롬이면 당연히 그 수는 팰린드롬이다. 예를 들어 12321 에서 232가 이미 팰린드롬인 걸 알고있다면 양쪽의 1 1 만 같은지 검사하면 된다.

처음에 반복문 범위를 잘못 설정해서 애를 먹긴했지만 아무튼 AC