[BOJ/DP] 백준 10942 - 팰린드롬? (Java)

10942 - 팰린드롬?

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

문제

ex. 칠판에 적은 수 1, 2, 1, 3, 1, 2, 1
- S = 1, E = 3 -> 1, 2, 1 (O)
- S = 2, E = 5 -> 2, 1, 3, 1 (X)
- S = 3, E = 3 -> 1 (O)
- S = 5, E = 7 -> 1, 2, 1 (O)

입력
첫째 줄: 수열의 크기 N (1 <= N <= 2,000)
둘째 줄: 칠판에 적은 수 N개 (<= 100,000)
셋째 줄: 질문의 개수 M (1 <= M <= 1,000,000)
넷째 줄 ~ M개의 줄: 질문 S, E
출력: 총 M개 줄에 걸쳐 팰린드롬 O -> 1 / X -> 0

---

풀이

DP

질문 M이 1,000,000개 -> 팰린드롬인지 검사하는 로직 1,000,000번 반복

=> 검사를 O(1)로 해야 함

IF. 한 번 검사할 때 O(N), 최대 크기 N 2,000 -> 2,000 * 1,000,000 = 20억 => 시간초과

=> 미리 계산해서 저장해야 함 -> DP

 

`dp[s][e]`: `arr[s~e]`가 팰린드롬이면 `true` (`s`: 시작 indx / e`: 끝 indx)

• 길이 1: 한 글자로 이뤄진 문자열 -> 무조건 팰린드롬 
• 길이 2: `arr[i] == arr[i + 1]` -> 팰린드롬 
• 길이 3 이상: 맨 앞 숫자 == 맨 뒤 숫자 -> 무조건 팰린드롬 (가운데 숫자 상관 X)
  • `arr[s] == arr[e] && dp[s + 1][e - 1]`
    • `dp[s][e]`를 채우려면 먼저 dp[s + 1][e - 1]`이 채워져 있어야 함
  • ex. A B A -> 앞뒤 모두 A-B-A
  • s = 2, e = 4 -> (길이 3) 2 3 4 / s + 1 = 3, e - 1 =3

boolean[][] dp = new boolean[N + 1][N + 1];

for (int i = 1; i <= N; i++) dp[i][i] = true;

for (int i = 1; i < N; i++) {
    if (arr[i] == arr[i + 1]) dp[i][i + 1] = true;
}

for (int len = 3; len <= N; len++) {
    for (int s = 1; s + len - 1 <= N; s++) {
        int e = s + len - 1;
        if (arr[s] == arr[e] && dp[s + 1][e - 1]) {
            dp[s][e] = true;
        }
    }
}

---

코드

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

// 팰린드롬?
public class boj_10942 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int N = Integer.parseInt(br.readLine());
        int[] arr = new int[N + 1];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        boolean[][] dp = new boolean[N + 1][N + 1];

        for (int i = 1; i <= N; i++) dp[i][i] = true;

        for (int i = 1; i < N; i++) {
            if (arr[i] == arr[i + 1]) dp[i][i + 1] = true;
        }

        for (int len = 3; len <= N; len++) {
            for (int s = 1; s + len - 1 <= N; s++) {
                int e = s + len - 1;
                if (arr[s] == arr[e] && dp[s + 1][e - 1]) {
                    dp[s][e] = 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());

            sb.append(dp[S][E] ? 1 : 0).append('\n');
        }

        System.out.println(sb);
    }
}