[BOJ] 10942. 팰린드롬? (🥇, DP)

🔗

풀이

질문의 개수는 최대 백만이고 수열의 크기가 2000이기 때문에 모든 질문에 대해서 매번 팰린드롬인지 여부를 확인하면 시간 초과가 발생할 수 있다. 그래서 규칙을 찾아서 S~E까지 팰린드롬인지를 한 번에 확인할 수 있도록 미리 메모이제이션을 통해 저장해둬야 풀 수 있는 문제.

팰린드롬은 가운데를 기준으로 양옆이 동일한 균형을 이루는 형태를 말하는데, 팰린드롬이 될 수 있는 조건을 잘 생각해보면 가운데가 동일할 때 양끝이 계속 동일한 형태로 확장되어 나가는 것이다. 정리하면 아래와 같다.

1. 양끝을 제외한 나머지 부분(가운데)이 팰린드롬이다
2. 양끝이 동일하다.

두 가지 조건을 모두 만족하는 형태는 그림과 같다. 이외에도 다른 조건이 있을 수 있겠지만 어쨌든 이 두 가지 조건을 크게 벗어나지는 않는다. 가장 처음 a의 위치를 S라고 하고 마지막 a의 위치를 E라고 했을 때 가운데 부분은 S+1 ~ E-1까지가 된다. 결국 어떤 수열에서 S~E가 팰린드롬인지를 확인하려면 아래 조건을 만족해야 한다.

1. S+1 ~ E-1까지가 팰린드롬이고
2. S와 E의 값이 동일할 때

dp[S][E]를 S~E가 팰린드롬인지 여부를 저장한다고 할 때, 점화식으로 나타내면 다음과 같다.

if (dp[S+1][E-1] == 1 && numbers[S] == numbers[E]) {
	dp[S][E] = 1;
}

참고로 S와 E가 1밖에 차이나지 않는 경우는 가운데를 비교할 필요 없이 S와 E만 같다면 팰린드롬을 이룬다. S=E인 경우에도 마찬가지이다. 이 두 값에 대해서는 미리 초기화한다.

import java.util.*;
import java.io.*;

public class Main {
    static int[] numbers;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        numbers = new int[N+1];
        numbers[0] = -1;
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= N; i++) {
            numbers[i] = Integer.parseInt(st.nextToken());
        }

        int[][] dp = new int[N+1][N+1];
        for (int j = 1; j <= N; j++) {
            dp[j][j] = 1;
            if (numbers[j] == numbers[j-1]) {
                dp[j-1][j] = 1;
            }

            for (int i = 1; i < j - 1; i++) {
                if (numbers[i] == numbers[j] && dp[i+1][j-1] == 1) {
                    dp[i][j] = 1;
                }
            }
        }

        int M = Integer.parseInt(br.readLine());
        int S; int E;
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            S = Integer.parseInt(st.nextToken());
            E = Integer.parseInt(st.nextToken());
            sb.append(dp[S][E] + "\n");
        }
        System.out.println(sb);
    }
}