[백준] 10942 팰린드롬? - JAVA

문제

명우는 홍준이와 함께 팰린드롬 놀이를 해보려고 한다.

먼저, 홍준이는 자연수 N개를 칠판에 적는다. 그 다음, 명우에게 질문을 총 M번 한다.

각 질문은 두 정수 S와 E(1 ≤ S ≤ E ≤ N)로 나타낼 수 있으며, S번째 수부터 E번째 까지 수가 팰린드롬을 이루는지를 물어보며, 명우는 각 질문에 대해 팰린드롬이다 또는 아니다를 말해야 한다.

예를 들어, 홍준이가 칠판에 적은 수가 1, 2, 1, 3, 1, 2, 1라고 하자.

• S = 1, E = 3인 경우 1, 2, 1은 팰린드롬이다.
• S = 2, E = 5인 경우 2, 1, 3, 1은 팰린드롬이 아니다.
• S = 3, E = 3인 경우 1은 팰린드롬이다.
• S = 5, E = 7인 경우 1, 2, 1은 팰린드롬이다.

자연수 N개와 질문 M개가 모두 주어졌을 때, 명우의 대답을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 수열의 크기 N (1 ≤ N ≤ 2,000)이 주어진다.

둘째 줄에는 홍준이가 칠판에 적은 수 N개가 순서대로 주어진다. 칠판에 적은 수는 100,000보다 작거나 같은 자연수이다.

셋째 줄에는 홍준이가 한 질문의 개수 M (1 ≤ M ≤ 1,000,000)이 주어진다.

넷째 줄부터 M개의 줄에는 홍준이가 명우에게 한 질문 S와 E가 한 줄에 하나씩 주어진다.

출력

총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다.

 

문제 개요

주어진 수열에서 특정 구간이 팰린드롬인지 빠르게 판별해야 하는 문제이다.
팰린드롬이란 앞에서 읽으나 뒤에서 읽으나 같은 수열을 의미한다.

예를 들어, [1, 2, 3, 2, 1]은 팰린드롬이지만 [1, 2, 3]은 아니다.
문제에서는 최대 1,000개의 수열과 최대 1,000,000개의 쿼리가 주어진다.

따라서 매 쿼리마다 직접 수열을 검사하면 시간 초과가 발생하게 된다.
이 문제는 다이나믹 프로그래밍(DP)을 활용하여 모든 가능한 구간의 팰린드롬 여부를 미리 계산함으로써 빠르게 쿼리를 처리할 수 있다.

 

핵심 아이디어: DP 테이블 구축

dp[i][j]를 arr[i]부터 arr[j]까지의 수열이 팰린드롬이면 1, 아니면 0으로 정의한다.
이를 위해 다음과 같은 점화식을 사용한다.

점화식 정리

1. 길이가 1인 구간은 항상 팰린드롬이다.
2. 길이가 2인 구간은 두 수가 같으면 팰린드롬이다.
3. 길이가 3 이상인 구간은
   양 끝이 같고, 안쪽 구간이 팰린드롬이라면 → 현재 구간도 팰린드롬이다.

 

예시로 보는 흐름

수열 arr = [1, 2, 3, 2, 1] 라고 가정하자.

Step 1. 길이 1: 자기 자신은 항상 팰린드롬

dp[1][1] = 1   // [1]
dp[2][2] = 1   // [2]
dp[3][3] = 1   // [3]
dp[4][4] = 1   // [2]
dp[5][5] = 1   // [1]

Step 2. 길이 2: 인접한 두 수가 같으면 팰린드롬

arr[1] == arr[2]? → 1 != 2 → X  
arr[2] == arr[3]? → 2 != 3 → X  
arr[3] == arr[4]? → 3 != 2 → X  
arr[4] == arr[5]? → 2 != 1 → X
→ 길이 2 팰린드롬 없음

Step 3. 길이 3 이상

길이 3

• arr[2] == arr[4] 이고 dp[3][3] == 1
  → dp[2][4] = 1 (즉, [2, 3, 2]는 팰린드롬)

길이 5

• arr[1] == arr[5] 이고 dp[2][4] == 1
  → dp[1][5] = 1 (즉, [1, 2, 3, 2, 1]은 팰린드롬)

 

결국

쿼리를 통해 구간이 팰린드롬인지 판별할 수 있다.

• 2 4 → dp[2][4] = 1 → 출력: 1
• 1 3 → dp[1][3] = 0 → 출력: 0
• 1 5 → dp[1][5] = 1 → 출력: 1

 

전체코드

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

public class Main {
    static int n, m;
    static int[] arr;
    static int[][] dp;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());

        arr = new int[n + 1];
        dp = new int[n + 1][n + 1]; // 1-based index

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

        // 길이 1
        for (int i = 1; i <= n; i++) {
            dp[i][i] = 1;
        }

        // 길이 2
        for (int i = 1; i < n; i++) {
            if (arr[i] == arr[i + 1]) {
                dp[i][i + 1] = 1;
            }
        }

        // 길이 3 이상
        for (int len = 3; len <= n; len++) {
            for (int start = 1; start <= n - len + 1; start++) {
                int end = start + len - 1;
                if (arr[start] == arr[end] && dp[start + 1][end - 1] == 1) {
                    dp[start][end] = 1;
                }
            }
        }

        m = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        for (int q = 0; q < m; q++) {
            st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            sb.append(dp[s][e]).append("\n");
        }
        System.out.print(sb);
    }
}

 

마무리

이 문제는 다이나믹 프로그래밍을 통해 효율적으로 구간 판별을 수행하는 대표적인 예시다.
팰린드롬 문제에서 "양 끝이 같고, 안쪽이 팰린드롬이면 전체도 팰린드롬이다"라는 점화식을 기억하면 유사 문제에 적용하기에도 좋다.