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

09 Jul 2023 in Algorithm on 다이나믹 프로그래밍

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

풀이

수열이 주어지고 수열의 S번째 수부터 E번째 까지 팰린드롬을 이루는지 확인하는 문제.

수열의 1번부터 N번까지의 팰린드롬 여부를 담는 dp배열을 만든다.

S, E를 입력받으면서 dp배열에 결과를 저장하면서 판별한다.

팰린드롬 판별은 재귀를 통해 구현했다.

S와 E가 같으면 한 자리수이므로 true이고,

아닌 경우 다시 재귀를 통해 S+1과 E-1의 팰린드롬 여부를 판별하도록 했다.

---

메모리: 219448KB

시간: 832ms

언어: Java 11

코드

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

public class Main {
    static int[] arr;
    static boolean[][] dp;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        arr = new int[N + 1];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 1; i < N + 1; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        int M = Integer.parseInt(br.readLine());
        dp = new boolean[N + 1][N + 1];
        StringBuilder sb = new StringBuilder();
        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] || pal(S, E)) {
                sb.append(1).append("\n");
            } else {
                sb.append(0).append("\n");
            }
        }

        System.out.println(sb);
    }

    private static boolean pal(int s, int e) {
        if (dp[s][e]) {
            return true;
        }

        if (s == e) {
            return  dp[s][e] = true;
        } else {
            if (arr[s] == arr[e]) {
                if (s + 1 == e || pal(s + 1, e - 1)) {
                    return dp[s][e] = true;
                } else {
                    return dp[s][e] = false;
                }
            } else {
                return dp[s][e] = false;
            }
        }
    }
}