[Java] BOJ 10942 - 팰린드롬?

 

 

BOJ 10942 - 팰린드롬? (https://www.acmicpc.net/problem/10942)

 

01. 🔎 문제 탐색

N: 수열의 크기 $(1 \leq N \leq 2,000)$
(각 원소는 100,000보다 작거나 같은 자연수)
M: 질문의 개수 $(1 \leq M \leq 1,000,000)$
S, E: 팰린드롬인지 판단할 부분 수열의 범위

01-1. 알고리즘 선택 & 시간 복잡도

• 각 범위에 대하여 양 끝을 제외한 부분수열이 팰린드롬인지 판단하고 양 끝을 비교하는 것으로 팰린드롬인지 알 수 있음
  -> 따라서, 이전 결과를 다음 결과에 이용하므로 DP로 풀 수 있음
• 예시로 S=1 E=5가 주어지고 S의 원소와 E의 원소가 같을 때 S+1, E-1의 부분수열이 팰린드롬이면 S, E의 부분수열 또한 팰린드롬이다.
• 이중 for문을 통해 모든 경우의 수를 구할 수 있으므로, 시간 복잡도 $O(N^2)$에 지배

02. 📝 코드 설계하기

1. 수열에 대해 입력하고 부분수열의 크기가 1일때는 항상 팰린드롬이므로 상태를 저장
2. 끝점을 고정시키고 시작점을 이동시키는 것으로 모든 경우의 수를 탐색하여 메모이제이션
   1. 시작점과 끝점이 같은 경우는 항상 팰린드롬이므로 continue
   2. 시작점과 끝점 사이에 있는 부분수열이 팰린드롬인지 판단하고, 아니라면 팰린드롬이 아니므로 continue
   3. 사이의 부분 수열이 팰린드롬이라면 시작점과 끝점의 원소를 비교해 같다면, 팰린드롬이 맞음

03. 🛠️ 시도별 수정

1회차

---

04. 🗝️ 정답 코드

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

public class Main {
  static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
  static StringTokenizer st;

  public static void main(String[] args) throws IOException {
    int N = Integer.valueOf(br.readLine());

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

    for(int i = 1; i <= N; i++){
      for(int j = 1; j <= i; j++){
        if(j == i) continue;
        if((j+1) <= (i-1) && dp[j+1][i-1] == 0) continue;

        dp[j][i] = (arr[j] == arr[i]) ? 1 : 0;
      }
    }

    int S, E;
    int M = Integer.valueOf(br.readLine());
    while(M-- > 0){
      st = new StringTokenizer(br.readLine());
      S = Integer.valueOf(st.nextToken());
      E = Integer.valueOf(st.nextToken());

      bw.write(dp[S][E] + "\n");
    }

    bw.flush();
    bw.close();
    br.close();
  }
}