백준 1509번 - 팰린드롬 분할

문제

백준 1509번 - 팰린드롬 분할

아이디어

• DP로 길이별 팰린드롬 구하는 방법을 통해 0부터 모든 길이까지 팰린드롬 배열을 구한다.
• dp[i]를 0부터 i까지 분할의 최소 개수라고 하고, 0부터 N-1 까지 팰린드롬 배열을 사용해 dp 배열을 채운다.
• 만약 0~i 까지가 팰린드롬이면 분할 개수는 1이다.
• 그렇지 않으면 1부터 i번째까지 팰린드롬인지를 확인하면서 팰린드롬이면 최솟값을 갱신한다.
• dp[i] = min(dp[i], dp[j] + 1) 이며, 0부터 j까지 팰린드롬에 현재 문자 하나를 추가한다는 것과 같다.

예상 시간 복잡도

• 예상 시간 복잡도 : O(N^2)

코드 구현

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

public class BJ_1509 {
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        char[] arr = br.readLine().toCharArray();

        int n = arr.length;

        boolean[][] isPalindrome = new boolean[n][n];

        //길이 1~2 팰린드롬
        for (int i = 0; i < n; i++) {
            isPalindrome[i][i] = true;

            if (i < n - 1 && arr[i] == arr[i + 1]) {
                isPalindrome[i][i + 1] = true;
            }
        }

        //길이 3~N 팰린드롬
        for (int i = n - 3; i >= 0; i--) {
            for (int j = i + 2; j < n; j++) {

                if (arr[i] == arr[j] && isPalindrome[i + 1][j - 1]) {
                    isPalindrome[i][j] = true;
                }
            }
        }

        int[] dp = new int[n];

        for (int i = 0; i < n; i++) {

            if (isPalindrome[0][i]) {
                dp[i] = 1;
            }
            else {
                dp[i] = Integer.MAX_VALUE;

                for (int j = 0; j < i; j++) {
                    if (isPalindrome[j + 1][i]) {
                        dp[i] = Math.min(dp[i], dp[j] + 1);
                    }
                }
            }
        }

        System.out.println(dp[n - 1]);
    }
}