[Baekjoon Online Judge] 10942번: 팰린드롬?

10942번: 팰린드롬?

요구사항

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

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

입력

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

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

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

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

출력

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

---

시간 제한이 있는 문제이기 때문에, 하나하나 루프를 돌며 팬린드롬인지 판별하기에는 너무 오랜 시간이 걸렸다. 즉 다이나믹 프로그래밍을 적용해야 하는데, 적절한 규칙을 찾아야 한다.

 

우선 (1  2  1)은 팰린드롬이다. 만약 판별하기 위한 값이 (?  1  2  1  ?) 라고 가정하면, ? ?의 숫자만 같다면 그 값은 팬린드롬에 만족하게 된다.

 

즉 숫자의 길이를 늘려가며 이전 값, index로 표현하면 (1 2 3 4 5) 중에 (2 3 4) 가 팬린드롬이면 1과 5의 숫자만 비교하여 판별하면 된다. 이것을 코드에 적용시켜보았다.

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Baekjoon10942 {

    public static void main(String[] args) throws IOException {

        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bufferedWriter = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(bufferedReader.readLine());
        int[] numbers = new int[n + 1];
        int[][] dp = new int[n + 1][n + 1];

        String[] input = bufferedReader.readLine().split(" ");
        for (int i = 1; i <= input.length; i++)
            numbers[i] = Integer.parseInt(input[i - 1]);

        for (int i = 1; i <= n; i++) // S ~ E의 길이가 1일 때, 팰린드롬에 만족한다.
            dp[i][i] = 1;

        for (int i = 1; i <= n - 1; i++) // S ~ E의 길이가 2일 때, 서로 같은 수이면 팰린드롬에 만족한다.
            if (numbers[i] == numbers[i + 1]) dp[i][i + 1] = 1;

        for (int i = 3; i <= n; i++) { // S ~ E의 길이가 3이상 일 때,
            for (int j = 1; j <= n - i + 1; j++) {
                int k = j + i - 1;

                // 현 위치의 값이 같고, 이전 값들이 팰린드롬에 만족해야 팰린드롬을 만족한다.
                if(numbers[j] == numbers[k] && dp[j + 1][k - 1] == 1)
                    dp[j][k] = 1;

            }
        }

        n = Integer.parseInt(bufferedReader.readLine());

        for (int i = 0; i < n; i++) {
            input = bufferedReader.readLine().split(" ");
            int s = Integer.parseInt(input[0]);
            int e = Integer.parseInt(input[1]);
            bufferedWriter.write(dp[s][e] + "\n");
        }

        bufferedWriter.flush();
        bufferedReader.close();
        bufferedWriter.close();
    }
}

 

참고로 S ~ E의 길이가 1인 경우 팰린드롬을 만족하기 때문에 dp 테이블에는 1이 들어간다. S ~ E의 길이가 2인 경우는 두 수의 값이 같은 경우, 팰린드롬에 만족하게 된다.

 

이제 S ~ E의 길이가 3 이상이고, S + 1과 E - 1의 값이 팰린드롬을 만족하며, S와 E index의 값이 같은지를 판별하여 해결하였다.