[백준] 🥇 10942 팰린드롬?

📌 난이도

🥇 Gold 4

📌 문제

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

📌 풀이

📌 Code

package BOJ.DP;


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

import static BOJ.DP.N2293_F.MakeDP;

public class N10942 {
    static int N;
    static int M;
    static int[] nums;
    static boolean[][] dp;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        N = Integer.parseInt(br.readLine());
        nums = new int[N];
        dp = new boolean[N][N];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            nums[i] = Integer.parseInt(st.nextToken());
        }
        MakeDP();
        M = Integer.parseInt(br.readLine());
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            if (dp[Integer.parseInt(st.nextToken()) - 1][Integer.parseInt(st.nextToken()) - 1]) {
                bw.write(1 + "\n");
            } else {
                bw.write(0 + "\n");
            }
        }
        bw.flush();
        bw.close();
    }

    static void MakeDP() {
        for (int i = 0; i < N; i++) {
            dp[i][i] = true;
            int range = i;
            range = Math.min(range, N - i - 1);
            for (int j = 1; j <= range; j++) {
                if (dp[i - j + 1][i + j - 1] && nums[i - j] == nums[i + j]) {
                    dp[i - j][i + j] = true;
                }
            }
        }
        for (int i = 1; i < N; i++) {
            if (nums[i - 1] == nums[i]) {
                dp[i - 1][i] = true;
            }
        }
        for (int i = 1; i < N - 1; i++) {
            int range = i;
            range = Math.min(range, N - i - 2);
            for (int j = 1; j <= range; j++) {
                if (dp[i - j + 1][i + j] && nums[i - j] == nums[i + j]) {
                    dp[i - j][i + j + 1] = true;
                }
            }
        }
    }
}

package (이름); 를 때고, class 이름을 Main으로 변경하면 된다.

📌 추가 예제

[Input]
12
1 2 1 3 1 2 1 1 1 1 1 1
10
1 3
2 5
3 3
5 7
5 5
1 7
8 12
8 11
8 10
8 9

[Output]
1
0
1
1
1
1
1
1
1
1

[Input]
12
1 1 1 1 1 1 1 1 1 1 1 1
10
1 2
2 3
1 5
4 8
2 5
6 8
1 10
2 12
2 2
9 12

[Output]
1
1
1
1
1
1
1
1
1
1

---

개인 공부 기록용 블로그입니다.
틀리거나 오류가 있을 경우 제보해주시면 감사하겠습니다.😁