[백준 1509] 팰린드롬 분할 / 자바 / dp(팰린드롬)

#문제         

레벨:  G1
알고리즘:  dp(팰린드롬)
풀이시간: 
힌트 참조 유무:

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

---

#문제 풀이        

팰린드롬 문자열의 정의: 처음 ~ 끝으로 읽으나 끝 ~ 처음으로 읽으나 같은 문자열

1. 팰린드롬 판별 배열palindrom[i][j](i ~ j까지 팰린드롬인지)을 저장한다.

 

2. 이중 for 문을 돌며 dp[i]값을 저장한다. dp[i] =1 ~ i까지 탐색했을 때 최소 팰린드롬 문자열의 조합 

예시)

초기화:
dp[0] = 0, dp[1~4] = MAX

end = 1 ("A" 까지):
start = 1: "A"는 팰린드롬
dp[1] = min(MAX, dp[0] + 1) = min(MAX, 0 + 1) = 1
dp: [0, 1, MAX, MAX, MAX]

end = 2 ("AB" 까지):
start = 1: "AB"는 팰린드롬 아님
start = 2: "B"는 팰린드롬
dp[2] = min(MAX, dp[1] + 1) = min(MAX, 1 + 1) = 2
dp: [0, 1, 2, MAX, MAX]

end = 3 ("ABB" 까지):
start = 1: "ABB"는 팰린드롬 아님
start = 2: "BB"는 팰린드롬
dp[3] = min(MAX, dp[1] + 1) = min(MAX, 1 + 1) = 2
start = 3: "B"는 팰린드롬
dp[3] = min(2, dp[2] + 1) = min(2, 2 + 1) = 2
dp: [0, 1, 2, 2, MAX]

end = 4 ("ABBA" 까지):
start = 1: "ABBA"는 팰린드롬
dp[4] = min(MAX, dp[0] + 1) = min(MAX, 0 + 1) = 1
start = 2: "BBA"는 팰린드롬 아님
start = 3: "BA"는 팰린드롬 아님
start = 4: "A"는 팰린드롬
dp[4] = min(1, dp[3] + 1) = min(1, 2 + 1) = 1
dp: [0, 1, 2, 2, 1]

---

#풀이 코드      

import java.io.*;
import java.util.Arrays;

public class Main {
   static String str;
   static int size;
   static boolean[][] palindrome;
   static int[] dp;
   
   public static void main(String[] args) throws IOException {
       BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
       BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
       
       str = br.readLine();
       size = str.length();
       palindrome = new boolean[size + 1][size + 1];
       dp = new int[size + 1];
       
       checkPalindrome();
       setDP();
       
       bw.write(String.valueOf(dp[size]));
       bw.flush();
       bw.close();
       br.close();
   }
   
   // DP[i]는 0~i까지의 문자열에서 만들 수 있는 팰린드롬 분할의 최소 개수
   static void setDP() {
       Arrays.fill(dp, Integer.MAX_VALUE);
       dp[0] = 0;
       
       // end: 현재 문자열의 끝 위치
       // start: 팰린드롬 시작 위치 
       for (int end = 1; end <= size; end++) {
           for (int start = 1; start <= end; start++) {
               // start부터 end까지가 팰린드롬이면
               if (palindrome[start][end]) {
                   // start-1까지의 최소 분할 횟수 + 현재 팰린드롬(1개)
                   dp[end] = Math.min(dp[end], dp[start - 1] + 1);
               }
           }
       }
   }
   
   // i~j 길이의 문자열이 팰린드롬인지를 판단하는 메소드
   static void checkPalindrome() {
       for (int i = 1; i <= size; i++) {
           for (int j = i; j <= size; j++) {
               boolean isSame = true;
               int from = i - 1;
               int to = j - 1;
               
               while (from <= to) {
                   if (str.charAt(from++) != str.charAt(to--)) {
                       isSame = false;
                       break;
                   }
               }
               
               if (isSame) {
                   palindrome[i][j] = true;
               }
           }
       }
   }
}