[백준 / BOJ] 10942번 : 팰린드롬? - JAVA

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

[10942번: 팰린드롬?

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

www.acmicpc.net](https://www.acmicpc.net/problem/10942)

DP

i부터 j까지의 숫자가 팰린드롬이라는 것을 확인하는 방법은 무엇일까? 만일 i번째 숫자와 j번째 숫자가 같은 경우, i + 1부터 j - 1까지가 팰린드롬이면, i부터 j까지도 팰린드롬이다. 이를 바탕으로 이차원 배열을 사용한 dp로 구현했다.

가장 먼저 팰린드롬인지 여부를 나타내는 2차월 배열 p를 init해준다. N의 최댓값이 2,000인데 비해 질문의 개수가 최대 1,000,000이기 때문에 먼저 초기화해주는 것이 빠를 것이라 판단했다.

INIT
1. 만일 start와 end가 같다면 원소 하나만을 갖는 배열이므로 p[start][end]는 팰린드롬이다(1)
2. num[start]와 num[end]가 같다면
- start + 1이 end인 경우 (즉 두 개가 나란히 있는 경우) p[start][end]는 팰린드롬이다.
- 그렇지 않다면 p[start + 1][end - 1]이 팰린드롬인 경우, p[start][end]도 팰린드롬이다.
만일 p[start + 1][end - 1]이 정의가 되어 있지 않다면(0) init(num, p start + 1, end - 1)을 진행한다.
3. p[start][end]의 값과 관계없이, [start + 1 ~ end], [start ~ end - 1]도 확인해준다.

이렇게 배열을 채워가면서, 만일 p[start][end]의 값이 0이 아닌 경우(이미 왔다간 경우)에는 바로 리턴하도록 한다. 리턴하지 않으면 시간 초과에 걸린다.

 

전체 코드

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

// 시간 : 772ms
// 메모리 : 242680KB
public class Main {

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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());

        int[] num = new int[N];
        int[][] p = new int[N][N];

        for (int i = 0; i < N; i++) {
            num[i] = Integer.parseInt(st.nextToken());
            p[i][i] = 1;
        }

        init(num, p, 0, N - 1);

        int M = Integer.parseInt(br.readLine());

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken()) - 1;
            int end = Integer.parseInt(st.nextToken()) - 1;

            if(p[start][end] == 1) sb.append("1\n");
            else sb.append("0\n");
        }

        System.out.println(sb);
    }

    private static void init(int[] num, int[][] p, int start, int end) {

        if(start > end) return;
        if(p[start][end] > 0) return;

        if(num[start] == num[end]) {
            if(start + 1 == end) {
                p[start][end] = 1;
            } else {
                if(p[start + 1][end - 1] == 0){
                    init(num, p, start + 1, end - 1);
                }
                p[start][end] = p[start + 1][end - 1];
            }
        } else {
            p[start][end] = 2;
        }
        init(num, p, start + 1, end);
        init(num, p, start, end - 1);
    }

}