[BaekJoon] 1509 팰린드롬 분할 (Java)

1.  문제 링크

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

2.  문제

3.  소스코드

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

public class Main {
    static String str;
    static boolean[][] palindrome; // idx1번째부터 idx2번째까지의 문자열이 팰린드롬인지의 여부
    static int[] dp; // index번째 위치까지의 팰린드롬 분할의 최소 개수

    static void input() {
        Reader scanner = new Reader();
        str = scanner.next();

        int len = str.length();
        palindrome = new boolean[len + 1][len + 1];
        dp = new int[len + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
    }

    static void solution() {
        findPalindrome(str, str.length());

		// 주어진 문자열에서 첫 번째 문자부터 end번째까지의 팰린드롬 분할의 최소 개수를 구한다
        // 첫 번째부터 end번째까지 팰린드롬 분할의 최소 개수를 구할 때에는
        // start + 1번째부터 end번째까의 부분 문자열이 팰린드롬이면서 dp[start]가 최소가 되는 경우를 찾아야 한다
        // 이렇게 구한 팰린드롬 분할의 최소 개수에 1을 더해주면 dp[end]가 된다
        // 그러므로 dp[end] = min(dp[start - 1]) + 1 이라는 점화식을 이용하여 팰린드롬 분할의 최소 개수를 구한다
        for(int end = 1; end <= str.length(); end++) {
            for(int start = 1; start <= end; start++) {
                if(palindrome[start][end])
                    dp[end] = Math.min(dp[end], dp[start - 1] + 1);
            }
        }

        System.out.println(dp[str.length()]);
    }

    static void findPalindrome(String str, int len) {
    	// 주어진 문자열에서 만들 수 있는 모든 연속된 부분 문자열을 순회하면서 해당 문자열이 팰린드롬인지 확인한다
        for(int start = 1; start <= len; start++) {
            for(int end = start; end <= len; end++) {
                boolean flag = true;

                int startIdx = start - 1, endIdx = end - 1;
                while(startIdx <= endIdx) {
                    if(str.charAt(startIdx++) != str.charAt(endIdx--)) {
                        flag = false;
                        break;
                    }
                }

                if(flag) palindrome[start][end] = true;
            }
        }
    }

    public static void main(String[] args) {
        input();
        solution();
    }

    static class Reader {
        BufferedReader br;
        StringTokenizer st;

        public Reader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while(st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }

            return st.nextToken();
        }
    }
}