[백준] 10942 팰린드롬? (Java)

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

문제 설명

팰린드롬 : 거꾸로 읽어도 똑같은 단어

- 숫자 배열을 줬을 때 주어진 범위 구간이 팰린드롬인지 아닌지 확인

조건

* 1 ≤ N ≤ 2,000
* M(질문의 개수) : 최대 백만

문제 해결 프로세스

1. 주어진 범위 구간에서 s인덱스와 e 인덱스 자리의 값이 같은지 확인

2. 같지 않다면 0.

3. 같다면 s + 1과 e-1 인덱스 비교

4. DP로 접근 (2차원 배열)

  - s와 e의 차가 2보다 작을 때는 s인덱스와 e인덱스만 비교해줘도 바로 팰린드롬인지 아닌지 알 수 있음

  - 2보다 커질 경우 s + 1과 e-1 인덱스를 매개변수로 두고 재귀 호출

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
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));
        StringBuilder sb = new StringBuilder();
        N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        arr = new int[N + 1];
        dp = new int[N + 1][N + 1];

        for (int i = 1; i <= N; i++) {
            Arrays.fill(dp[i], -1);
        }
        for (int i = 1; i <= N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
            dp[i][i] = 1;
        }
        M = Integer.parseInt(br.readLine());
        for (int i = 0; i < M; i++) {
            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);
    }

    public static int dp(int s, int e) {
        if (dp[s][e] != -1) return dp[s][e];
        if (arr[s] != arr[e]) return dp[s][e] = 0;
        if (e - s <= 2) {
            return dp[s][e] = (arr[e] == arr[s]) ? 1 : 0;
        }
        return dp[s][e] = dp(s + 1, e - 1);
    }

}