[BOJ 백준] 10942번 팰린드롬?

문제

BOJ 10942 : https://www.acmicpc.net/problem/10942

10942번: 팰린드롬?

접근

* 팰린드롬(palindrome)이란 'eye'처럼 역순으로 읽어도 같은 말이나 구절 또는 숫자이다. (우리말로는 '회문(回文)'으로 번역된다)

이 문제의 테스트케이스는 최대 2,000개이므로 처음부터 모든 경우에 대해 팰린드롬을 찾아놓은 뒤 테스트 케이스에 대한 답을 내놓기로 했다.

칠판에 쓰인 숫자를 앞에서부터 순차적으로 임의의 위치에 대해 홀수개의 팰린드롬인 경우와 짝수개의 팰린드롬인 경우를 검사해준다. 만약 팰린드롬이 가능하다면 왼쪽과 오른쪽으로 확장해나가면서 계속 팰린드롬을 찾아주면 된다. 이런 식으로 팰린드롬이 가능한 모든 경우의 수를 찾아 둔 뒤 들어오는 테스트 케이스에 대해 팰린드롬 유무를 출력해 준다.

 

코드

// algorithm study
// BOJ_10942_팰린드롬?

#include <iostream>
#include <vector>

using namespace std;

int n, f[2010][2010] = {0};
vector<int> num;

void same(int l, int r) {
    while (l >= 0 && r < n && num[r] == num[l]) {
        f[l][r] = 1;
        f[r][l] = 1;
        l--;
        r++;
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    cin >> n;
    for (int i = 0; i < n; i++) {
        int t;
        cin >> t;
        num.push_back(t);
        f[i][i] = 1;
    }
    for (int i = 0; i < n; i++) {
        int l = i - 1;
        int r = i + 1;
        same(l, r);
        l = i;
        r = i + 1;
        same(l, r);
    }
    
    int t;
    cin >> t;
    for (int i = 0; i < t; i++) {
        int a, b;
        cin >> a >> b;
        cout << f[a - 1][b - 1] << "\n";
    }
    return 0;
}

 

깃 허브 주소 : https://github.com/algoribi/algorithm-study