BOJ (Java) 10942번: 팰린드롬?

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

---

풀이

M이 최대 1,000,000개 이므로 M이 들어올 때마다 팰린드롬인지 판단할 수는 없다. (시간제한 0.5초)따라서 모든 경우의 수에 대해 팰린드롬인지 저장한 후, 범위값이 들어오면 저장된 값을 불러와야 한다.

 

팰린드롬이란 중간을 기준으로 인덱스를 양 방향으로 이동했을 때 값이 같아야 한다.따라서 (1, 6)가 팰린드롬이라면 (2, 5), (3, 4) 또한 팰린드롬이어야 한다.이를 바탕으로 점화식을 세운다면 dp[s][e] = dp[s + 1][e - 1] && (nums[s] == nums[e]) 가 된다.이 때 s와 e의 차이가 2 미만일 경우는 dp 검증을 제외해줬다.

 

dp[s][e]를 구할 때 dp[s + 1][e - 1]의 값이 필요하므로 이중 반복문에서 겉의 값을 end 값으로 지정, 

end를 고정한 후 start 값을 먼저 이동하며 값을 채워줬다.

위와 같은 순서로 값을 채워줬다.

---

Java 코드

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

public class Main {
    private static int[] nums;
    private static boolean[][] dp;
    private static int N, M;
    public static void main(String[] args) throws IOException {

        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(bf.readLine());

        nums = new int[N];
        dp = new boolean[N][N];
        String[] inputs = bf.readLine().split(" ");
        for (int i = 0; i < N; i++) {
            nums[i] = Integer.parseInt(inputs[i]);
            Arrays.fill(dp[i], false);
            dp[i][i] = true;
        }

        // 모든 원소에 대해 팰린드롬인지 파악 후 이를 dp 배열에 저장
        for (int e = 0; e < N; e++) {
            for (int s = 0; s < e; s++) {
                if (e - s > 2) {
                    dp[s][e] = (nums[s] == nums[e]) && dp[s + 1][e - 1];
                } else {
                    dp[s][e] = (nums[s] == nums[e]);
                }
            }
        }

        // M개의 수 판단
        M = Integer.parseInt(bf.readLine());
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < M; i++) {
            inputs = bf.readLine().split(" ");
            int s = Integer.parseInt(inputs[0]) - 1;
            int e = Integer.parseInt(inputs[1]) - 1;

            // 팰린드롬이라면 1, 아니라면 0을 StringBuilder에 저장
            if (dp[s][e]) {
                sb.append("1\n");
            } else {
                sb.append("0\n");
            }
        }
        
        // 저장한 값을 한 번에 출력
        System.out.println(sb);
    }
}