[BaekJoon] 2079 팰린드롬 (Java)

1.  문제 링크

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

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 word;
    // palindrome[start][end] = start번째 문자부터 end번째 문자까지의 문자열이 팰린드롬인지 여부
    static boolean[][] palindrome;

    static void input() {
        Reader scanner = new Reader();

        word = scanner.nextLine();
        palindrome = new boolean[word.length() + 1][word.length() + 1];
    }

    static void solution() {
        findPalindrome();
        System.out.println(getMinNumOfPartialPalindrome());
    }

    static int getMinNumOfPartialPalindrome() {
        // dp[idx] = idx번째 문자까지 해당 문자열을 최소 개수의 팰린드롬으로 나눴을 때의 팰린드롬 수
        int[] dp = new int[word.length() + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;

        // 끝 문자를 첫 번째 문자부터 하나씩 늘려가며 잡고
        // 시작 문자는 첫 번째 문자부터 끝 문자까지 늘려가며
        // 각 시작 문자 ~ 끝 문자 문자열이 팰린드롬인지 확인한 후
        // 팰린드롬이 맞다면 해당 문자열은 하나의 팰린드롬이 될 수 있으므로
        // 해당 시작 문자 바로 이전까지 문자열들에서 나눠진 팰린드롬 개수에 1을 더해주면 끝 문자까지의 팰린드롬 개수를 구할 수 있다
        // 이를 시작 문자 위치가 끝 문자 위치가 될 때까지 반복하면서 그 중 최솟값을 dp에 저장한다
        // if palindrome[start][end] => dp[end] = min(dp[end], dp[start - 1] + 1)
        for(int end = 1; end <= word.length(); end++) {
            for(int start = 1; start <= end; start++) {
                if(palindrome[start][end])
                    dp[end] = Math.min(dp[end], dp[start - 1] + 1);
            }
        }

        return dp[word.length()];
    }

    // 각 문자열에 대하여 문자열이 팰린드롬인지 구하는 메서드
    static void findPalindrome() {
        // 첫 번째 문자부터 시작 문자로 잡고 시작 문자를 기준으로 이후의 문자들을 하나씩 추가하면서
        // 그러한 문자열이 팰린드롬인지 확인하고 팰린드롬이라면 palindrome의 값을 true로 변경한다
        for(int start = 1; start <= word.length(); start++) {
            for(int end = start; end <= word.length(); end++) {
                // 팰린드롬을 판별하기 위해 가장 처음 문자와 가장 끝 문자를 비교하고
                // 가장 처음 문자는 뒤로 한 칸, 끝 문자는 앞으로 한 칸 움직이며 문자를 비교한다
                // 만약 다른 문자가 나온다면 이는 팰린드롬이 아니라는 뜻이므로 다른 문자가 없는 경우에 대해서만 palindrome 값을 true로 변경한다
                int startIdx = start - 1, endIdx = end - 1;
                boolean flag = true;
                while(startIdx <= endIdx) {
                    if(word.charAt(startIdx++) != word.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 nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }

            return str;
        }
    }
}