BOJ 10942 팰린드롬?(JAVA) 🔁

문제 링크

10942번: 팰린드롬?

문제 설명

주어진 수열이 s부터 e까지 팰린드롬이 맞냐? 아니냐?를 따지는 문제

입력

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

출력

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

구조화

dp[s][e]에 저장(메모이제이션 사용)

오답 노트

메모이제이션 연습 하기!

소스 코드

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

public class Main {
    public static int[] arr;
    public static boolean[][] dp; // s부터 e까지 팰린드롬 유무 저장
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int 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());
        }
        
        // 팰린드롬 유무 저장 단계
        for (int i = 1; i <= N; i++) {
            dp[i][i]=true;
            if(arr[i]==arr[i-1]){
                dp[i-1][i] = true;
            }
        }

        // i는 s와 e 사이의 거리
        for (int i = 2; i <= N-1; 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;
                }
            }
        }
        
        // 홍준이의 질문
        int 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());

            if(dp[s][e]) sb.append(1);
            else sb.append(0);

            sb.append("\n");
        }
        
        System.out.println(sb);
    }

}