[백준 10942] 팰린드롬?

문제 링크: https://www.acmicpc.net/problem/10942

---

풀이

다이나믹 프로그래밍 문제였다. 부분 수열의 팰린드롬 여부를 이용하면 전체 수열의 팰린드롬 여부를 구할 수 있기 때문이다.

 

(1) 점화식 세우기

부분 수열을 이용해 현재 수열의 팰린드롬 여부를 어떻게 확인할 수 있을까?

1. 양 끝 숫자를 제외한 부분 수열이 팰린드롬이고,
2. 양 끝 숫자가 같으면
해당 수열도 팰린드롬이다.

이를 코드로 나타내면 다음과 같다.

 

if(dp[i+1][j-1]==1 && num[i]==num[j]) {
    dp[i][j] = 1;
}

 

여기서 인덱스 에러를 방지하려면 i+1 <= j-1이어야 하므로, 2 <= j-i가 된다.
따라서 길이가 2 이하인 부분수열은 dp값을 따로 초기화시켜주어야 한다.

 

(2) 초기화

길이가 1인 부분수열은 항상 팰린드롬이다. 따라서 항상 dp[i][i]=1이다.
길이가 2인 부분수열은 두 숫자가 같으면 팰린드롬이다. 따라서 if(num[i]==num[i+1]) dp[i][i+1]=1이 된다.

길이가 2 이하인 모든 부분수열의 팰린드롬 여부를 구하는 반복문 하나를 추가하면 아래와 같이 코드를 작성할 수 있다.

 

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

 

---

전체 코드

 

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

public class Main_10942_팰린드롬 {
    static int N, M;
    static int[] num;
    static int[][] dp;
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

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

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


        M = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        for (int i=0; i<M; i++) {
            st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken())-1;
            int e = Integer.parseInt(st.nextToken())-1;
            sb.append(dp[s][e] + "\n");
        }
        System.out.println(sb.toString());
    }
}