[JAVA] 백준1509번 "팰린드롬 분할"

boj1509	https://www.acmicpc.net/problem/1509

문제

세준이는 어떤 문자열을 팰린드롬으로 분할하려고 한다. 예를 들어, ABACABA를 팰린드롬으로 분할하면, {A, B, A, C, A, B, A}, {A, BACAB, A}, {ABA, C, ABA}, {ABACABA}등이 있다.

분할의 개수의 최솟값을 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 문자열이 주어진다. 이 문자열은 알파벳 대문자로만 이루어져 있고, 최대 길이는 2,500이다.

출력

첫째 줄에 팰린드롬 분할의 개수의 최솟값을 출력한다.

---

접근방법 또는 고려해야할 점

dp 2개를 사용함

dp1[i][j] = arr[i] ~ arr[j] 까지가 팰린드롬인지 확인하는 로직

dp1[start][start+len] =

dp1[start][start+len] = (arr[start] == arr[start+len] && dp1[start+1][start+len-1]);

dp2[N] = arr[0] ~ arr[N] 까지 팰린드롬 분할 최소 길이를 기록해놓는 로직

만약 dp1[j][N]이 팰린드롬이면 dp2[j-1]+1 이 최솟값인지 확인해야함.

dp2[N] = Math.min(dp2[N], dp2[j-1] + 1);

---

코드

package self;

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

public class boj1509 {
    static char[] arr;
    static int N;
    static boolean[][] dp1;
    static int[] dp2;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        arr = br.readLine().toCharArray();
        N = arr.length;
        dp1 = new boolean[N][N];
        dp2 = new int[N];

        for(int i = 0 ; i<N; i++){ // dp1 배열 초기화
            dp2[i] = i+1; // dp2 배열 최악의 경우 팰린드롬 분할 길이로 초기화
            if(i == N-1){
                dp1[i][i] = true;
                break;
            }
            dp1[i][i] = true;
            if(arr[i] == arr[i+1]) dp1[i][i+1] = true;
        }

        for(int len = 2 ; len < N ; len++){ // start ~ start+len 이 팰린드롬인지 확인하는 DP
            for(int start = 0; start+len<N; start++){
                dp1[start][start+len] = (arr[start] == arr[start+len] && dp1[start+1][start+len-1]);
            }
        }

        for(int i = 0; i<N; i++){
            for(int j = 0; j<=i; j++){
              if(dp1[j][i]){// 팰린드롬이면?
                  if(j==0) dp2[i] = 1;
                  else{
                      dp2[i] = Math.min(dp2[i], dp2[j-1] + 1);
                  }
              }
            }
        }

        System.out.println(dp2[N-1]);

    }
}