[백준] Q1509 팰린드롬 분할 JAVA

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

1509번: 팰린드롬 분할

1. 문제의 유형 및 이해

dp

어떤 문자열을 팰린드롬으로만 분할하려고할 때, 분할 개수의 최소값을 구하는 문제이다.

문자열의 최대길이는 2500.

예를 들어, ABACABA를 팰린드롬으로 분할하면, {A, B, A, C, A, B, A}, {A, BACAB, A}, {ABA, C, ABA}, {ABACABA}등이 있다.

 

어떤 문자열에서 범위 (i,j)에 대해 새로운 문자열 j+1번째를 볼 때, 생길 수 있는 경우의 수는

1. (i,j+1)이 팰린드롬인 경우

2.  j+1이 들어옴으로써 (i~j)사이의 k 값부터 팰린드롬이 생기는 경우 (i~k)(k~j)

3. 또는 아무런 변화가 없는 경우

dp[i] = 어떤 i까지의 최소 팰린드롬 분할 개수 라고 했을 때 각각의 경우를 하나로 합치면 다음과 같은 점화식을 만들 수 있습니다.

dp[i] = Math.min(dp[i], dp[k-1]+1)( 0<=k<=i) 로 정의할 수 있습니다.

2. 문제 접근 방법

dp[i] = Math.min(dp[i], dp[k-1]+1)( 0<=k<=i) 의 점화식을 조금 더 본다면, 

0~i사이의 어떤 k값까지 팰린드롬이 생긴다면 (0~k-1)(k~j)로 분할이 되고, 

dp[k-1]은 dp 정의 에 따라 가장 최소 팰린드롬 분할개수를 가지고 k~j는 하나의 값을 가집니다.

 

이렇게 구현하기 위해 우리가 알아야하는 것은, 임의의 i,j에 대해 팰린드롬인지 빠르게 확인할 수 있어야 합니다.

 

팰린드롬? 문제 를 참조하고 풀어보시면 큰 도움이 될 것 같습니다.

 

이전에 재귀로 풀었을 때의 팰린드롬? 을 적용하여 문제를 풀었을 때 문제점은 true임은 보장이 되지만, false일때는 보장하지 못한다는 데에 있었습니다. 그렇기 떄문에 만약 AAAAAAAAAAAAAAAAAAAAAAAAAAAKCCAAAAAAAAAAAAAAAAAAAAAAAAA와 같은 문자열이 있을 때 0~마지막 까지는 항상 팰린드롬이 아니지만 C를 만날 때 까지 반복적으로 다시 계산한다는 점이 문제였습니다.

정확하게 memoization을 하지 못했기 때문에, 이 문제에서는 조금 더 보완하여 모든 질의에 O(1)에 응답가능하도록 미리 다 구해두고 바로 참조가능하도록 구현하였습니다.

 

이전의 Top-down 방식에서 bottom-up방식으로 변경하여 구현하여 true, false에 모두 보장가능하도록 하였습니다.

 

정리하자면,

1. dp[i] = Math.min(dp[i], dp[k-1] +1) (0<=k<=i)

2. 이를 구현하기 위해 어떤 (k~i)가 팰린드롬인지 빠르게 확인가능해야함.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
/**
 * @author : pcrmcw0486
 * @문제번호 : Q1509
 * @문제이름 : 팰린드롬 분할
 * @난이도 : Gold I
 * @date : 2022-02-27 오후 2:55
 * @문제이해 어떤 문자열을 팰린드롬으로 분할하려고 한다.
 * ABACABA 를 분할하면 ABACABA {A, BACAB, A}, {ABA, C, ABA}, {A,B,A,C,A,B,A}
 * 분할 개수의 최소값을 찾으시오.
 * 주어지는 문자열을 모두 대문자이고, 최대 길이는 2500이다.
 * @알고리즘 dp
 * @접근방법
 * dp[x] 를 x까지의 팰린드롬 분할 최소 횟수라고 하자.
 * 어떠한 x+1을 포함한 최장 팰린드롬을 이루는 idx i라고 한다면
 * dp[i-1] + 1 과 현재 값 +1을 비교하여 더 작은 값이 된다.
*/
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        char[] text = br.readLine().toCharArray();
        boolean[][] check = new boolean[text.length][text.length];
        int[] dp = new int[text.length];
       
       //팰린드롬 확인을 위한 check[][] 배열
        for (int i = 0; i < text.length; i++) {
            check[i][i] = true;
            if (i != text.length - 1) {
                check[i][i + 1] = text[i] == text[i + 1];
            }
        }
        for (int i = 2; i < text.length; i++) {
            for (int j = 0; j < text.length-i; j++) {
                if (text[j] != text[i + j]) continue;
                check[j][j + i] = check[j + 1][j + i - 1];
            }
        }

		
        //dp[i] = Math.min(dp[i], dp[i-1] +1)
        // 0일 때(0~i)가 팰린드롬이라면 더 볼 필요가 없다고 생각해서 continue했습니다.
        dp[0] = 1;
        for (int i = 1; i < text.length; i++) {
            dp[i] = dp[i-1] +1;
            if(check[0][i]){
                dp[i] = 1;
                continue;
            }
            for (int j = 1; j <= i; j++) {
                if (check[j][i]) {
                    dp[i] = Math.min(dp[i], dp[j - 1] + 1);
                }
            }
        }
        
        System.out.println(dp[dp.length-1]);
    }
}