[백준] BOJ_10942 팰린드롬?

1. 문제 정보

• 문제 요약: 자연수 개가 나열된 수열에서, 번째부터 번째까지의 수가 팰린드롬을 이루는지 판별하는 쿼리를 해결해야 합니다.
• 주요 제약: 수열의 크기 $N \le 2,000$, 질문의 개수 $M \le 1,000,000$.
• 난이도: Gold IV
• 원본 링크: BOJ 10942 - 팰린드롬?

---

2. 접근 방식

1) 문제의 본질

이 문제의 핵심은 질문(Query)의 횟수에 있습니다. 만약 매 질문마다 $O(N)$의 시간 복잡도로 팰린드롬 여부를 직접 검사한다면, 전체 시간 복잡도는 $O(M \times N)$이 되어 약 20억 번의 연산이 필요합니다. 이는 0.5초(또는 일반적인 1~2초) 제한 내에 절대 통과할 수 없는 수치입니다.

따라서 우리는 전처리(Pre-processing)를 통해 모든 구간에 대한 팰린드롬 여부를 미리 계산해 두어야 합니다. 이때 발생하는 중복 계산을 제거하기 위해 DP를 사용합니다.

2) 알고리즘 설계

팰린드롬은 양 끝이 같고, 그 사이의 부분 수열이 다시 팰린드롬이어야 한다는 순환 의존성을 가집니다.

• 길이가 1인 경우: 무조건 팰린드롬입니다.
• 길이가 2인 경우: 두 수가 같으면 팰린드롬입니다.
• 길이가 3 이상인 경우: arr[S] == arr[E] 이고, 그 사이인 [S+1, E-1] 구간이 팰린드롬이면 전체도 팰린드롬입니다.

3) 점화식

$isPalindrome[i][j]$를 번째부터 번째까지의 팰린드롬 여부라고 할 때:

1. 기저 사례 (Base Case):

• $isPalindrome[i][i] = true$ (길이 1)
• $isPalindrome[i][i+1] = (arr[i] == arr[i+1])$ (길이 2)

2. 일반 점화식 (Length $\ge$ 3):

• $isPalindrome[i][j] = (arr[i] == arr[j]) \land isPalindrome[i+1][j-1]$

---

3. 코드 구현

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;

    public static void main(String[] args) throws IOException {
        int N = Integer.parseInt(br.readLine());
        int[] arr = new int[N + 1];

        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        boolean[][] isPalindrome = new boolean[N + 1][N + 1];

        // 1. 길이가 1인 경우 초기화
        for (int i = 1; i <= N; i++) {
            isPalindrome[i][i] = true;
        }

        // 2. 길이가 2인 경우 초기화
        for (int i = 1; i < N; i++) {
            if (arr[i] == arr[i + 1]) {
                isPalindrome[i][i + 1] = true;
            }
        }

        // 3. 길이가 3 이상인 경우 (Bottom-up DP)
        for (int len = 3; len <= N; len++) {
            for (int i = 1; i <= N - len + 1; i++) {
                int j = i + len - 1;

                // 양 끝값이 같고, 그 사이 구간(i+1, j-1)이 팰린드롬이면 true
                if (arr[i] == arr[j] && isPalindrome[i + 1][j - 1]) {
                    isPalindrome[i][j] = true;
                }
            }
        }

        int M = Integer.parseInt(br.readLine());
        var sb = new StringBuilder();

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());

            // 전처리된 결과를 O(1)에 조회
            sb.append(isPalindrome[s][e] ? 1 : 0).append('\n');
        }

        System.out.println(sb);
    }
}

---

4. 회고 및 배운 점

시간 복잡도 분석

• 전처리 단계: 2차원 배열을 채우는 과정이므로 $O(N^2)$입니다. $2,000^2 = 4,000,000$으로 충분히 빠릅니다.
• 쿼리 단계: 각 질문에 대해 이미 계산된 배열 값을 참조만 하므로 $O(1)$입니다. 전체 질문에 대해 $O(M)$입니다.
• 최종 복잡도: $O(N^2 + M)$. 단순 검사 시 $O(N \times M)$이었던 복잡도를 획기적으로 낮추어 대량의 쿼리를 처리할 수 있게 되었습니다.

구현 디테일

1. DP 채우기 순서: $isPalindrome[i][j]$를 구하기 위해 $isPalindrome[i+1][j-1]$이라는 더 짧은 길이의 부분 문제 결과가 필요합니다. 따라서 루프를 돌 때 나 가 아닌 길이(len)를 기준으로 바깥 루프를 구성한 것이 이 문제 해결의 핵심입니다.