[BaekJoon] 백준 10942번 펠린드롬 ? (Java)

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

10942번: 팰린드롬?

 

 

 

펠린드롬이란 순서대로 or 거꾸로 읽어도 같은 수를 말한다. 

 

반복문을 돌면서 직접 비교할 수도 있지만 질문의 개수를 보면 1,000,000 으로 시간초과를 피해 다이나믹 프로그래밍으로 풀어야 한다. 

 

P[s][e] 를 s 번째부터 e 번째까지의 펠린드롬 true/false 값이라고 한다면

이는 s, e 에 위치한 숫자간 펠린드롬 && P[s+1][e-1] 으로 나타낼 수 있다. 

 

출력해야 하는 답이 많기 때문에 println이 아닌 StringBuffer 로 처리해줘야 한다. 

 

---

반복문 >> 

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

public class Main {
    static boolean[][] P;
    static int[] number;
    static int N;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        number = new int[N+1];
        
        String[] input = br.readLine().split(" ");
        for(int i = 1; i<=N; i++) {
            number[i] = Integer.parseInt(input[i-1]);
        }
        P = new boolean[N+1][N+1];
        
        // 길이가 1 및 2일 때
        for(int i = 1; i<=N; i++) {
            P[i][i] = true;
            
            if (i < N) {
                P[i][i+1] = number[i] == number[i+1];
            }
        }
        
        // 길이가 3 이상일 때
        for(int len = 2; len<N; len++) {
            for(int j = 1; j<=N-len; j++) {
                P[j][len+j] = number[j] == number[len+j] && P[j+1][len+j-1];
            }
        }
    
        StringBuilder builder = new StringBuilder();
        
        int M = Integer.parseInt(br.readLine());
        for(int i = 0; i<M; i++) {
            String[] ip = br.readLine().split(" ");
            int s = Integer.parseInt(ip[0]);
            int e = Integer.parseInt(ip[1]);
            builder.append(P[s][e] ? "1" + "\n" : "0" + "\n");
        }
    
        System.out.println(builder);
    }
}

 

 

---

재귀 >>

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

public class Main {
    static int[][] P;
    static int[] number;
    static int N;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        number = new int[N+1];
        
        String[] input = br.readLine().split(" ");
        for(int i = 1; i<=N; i++) {
            number[i] = Integer.parseInt(input[i-1]);
        }
        P = new int[N+1][N+1];
        
        for(int i = 1; i<=N; i++) {
            for(int j = i; j<=N; j++) {
                if (i == j) {
                    P[i][j] = 1;
                } else if (i + 1 == j) {
                    P[i][j] = number[i] == number[j] ? 1 : 0;
                } else {
                    P[i][j] = -1;
                }
            }
        }

        StringBuilder builder = new StringBuilder();
        
        int M = Integer.parseInt(br.readLine());
        for(int i = 0; i<M; i++) {
            String[] ip = br.readLine().split(" ");
            int s = Integer.parseInt(ip[0]);
            int e = Integer.parseInt(ip[1]);
            dp(s, e);
            builder.append(P[s][e] == 1 ? "1" + "\n" : "0" + "\n");
        }
    
        System.out.println(builder);
    }
    
    public static int dp(int s, int e) {
        if ( s < 1 || e > N+1 || s > e) {
            return 0;
        }
    
        if (s != e) {
            if (P[s][e] == -1) {
                int pre = dp(s + 1, e - 1);
                int tmp = number[s] == number[e] ? 1 : 0;
            
                P[s][e] = pre == 1 && tmp == 1 ? 1 : 0;
            }
        }
        return P[s][e];
    }
    
}