[BOJ]10942 - 팰린드롬?(G4)

문제 링크

10942-팰린드롬?

입력

첫째 줄에 수열의 크기 N (1 ≤ N ≤ 2,000)이 주어진다.
둘째 줄에는 홍준이가 칠판에 적은 수 N개가 순서대로 주어진다. 칠판에 적은 수는 100,000보다 작거나 같은 자연수이다.
셋째 줄에는 홍준이가 한 질문의 개수 M (1 ≤ M ≤ 1,000,000)이 주어진다.
넷째 줄부터 M개의 줄에는 홍준이가 명우에게 한 질문 S와 E가 한 줄에 하나씩 주어진다.

출력

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

문제 풀이

dp를 사용해서 문제를 해결
2차원 배열을 만들어서

• 길이가 1인 경우 즉 dp[i][i]의 경우에는 모두 true
• 길이가 2인 경우에는 바로 앞의 문자와 비교해서 같다면 true, 아니면 false
• 길이가 2이상인 경우에는 dp[i][j]를 확인하는데 이때 i를 시작 문자, j를 마지막 문자로 생각

천천히 생각해보면 어렵지 않게 풀 수 있는 문제였다!

*StringBuilder 가 아니라 System.out.println() 을 사용하니깐 시간 초과가 발생

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

public class Main {

    static int N, M, S, E;
    static int[] arr;
    static boolean[][] 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 boolean[N + 1][N + 1];

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

        solve();
        M = Integer.parseInt(br.readLine());
        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]==true ? "1\n" : "0\n");
        }
        System.out.println(sb);

    }

    public static void solve() {
        for (int i = 1; i <= N; i++)
            dp[i][i] = true;

        for (int i = 1; i <= N - 1; i++)
            if (arr[i] == arr[i + 1]) dp[i][i + 1] = true;

        for (int i = 2; i < N; i++) {
            for (int j = 1; j <= N - i; j++) {
                if (arr[j] == arr[j + i] && dp[j + 1][j + i - 1])
                    dp[j][j + i] = true;
            }
        }
    }
}