BOJ(백준 온라인 저지) 1509번 with 자바[JAVA]

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

---

분할정복이다.

 

문제 이해

 

우선 팰린드롬 분할의 수가 최소가 되려면 일반적으로 팰린드롬 분할들의 길이가 길면 된다.

팰린드롬 분할들의 길이가 길면 당연히 분할의 수가 반대로 줄어들기 때문이다.

 

그렇다면 팰린드롬의 길이를 늘릴 방법은 무엇일까?

 

우선 팰린드롬이 되는 조건먼저 살펴보자

 

조건

 

팰린드롬은 첫 문자와 마지막 문자가 일단 같아야한다.

예를 들어

 

{A, B, A} 는 팰린드롬이다. 첫 문자와 마지막 문자가 같기 때문이다.

{A} 는 팰린드롬이다. 첫 문자이자 마지막 문자가 A로 같기 때문이다.

 

하지만, 위 조건만으로는 부족하다.

예를 들어

 

{A, B, C, A} 는 팰린드롬이 아니다. 첫 문자와 마지막 문자가 같아도 말이다.

 

그 다음 조건으로는 첫 문자와 마지막 문자 사이에 있는 문자들이 팰린드롬이거나 없어야 한다.

예를 들어

 

{A, C, B, C, A} 는 팰린드롬이다. 첫 문자와 마지막 문자가 같고, 사이에 문자열인 {C, B, C} 도 팰린드롬이기 때문이다.

{A, A} 는 팰린드롬이다. 첫 문자와 마지막 문자가 같고, 사이에 문자열이 없기 때문이다.

 

구현

 

팰린드롬인지 아닌지...

 

해당 문자열이 팰린드롬인지 아닌지는 P[i][j] 를 통해 알 수 있다.

해당 배열은 i 번째 문자열부터 j 번째 문자열까지의 문자열이 팰린드롬인지 아닌지를 알려주는 boolean 2차원 배열이다.

 

위에 팰린드롬 조건들이 충족된다면 P[i][j] 값을 true 로 바꿔주는 방식을 사용한다.

 

팰린드롬 분할의 수...

 

우리는 문자를 하나하나 입력받아 만들 수 있는 팰린드롬 분할들 중 가장 적은 분할 수를 저장할 것이다.

그러면, 만들 수 있는 팰린드롬 분할의 수는 어떻게 구할까?

 

일단 새롭게 받는 문자를 통해 만들 수 있는 팰린드롬이 무엇이 있는지 확인한다.

그리고 팰린드롬을 만들 수 있다면, 그 문자 전까지의 최소 팰린드롬 수 + 1 을 한 값이

새롭게 받은 문자를 통해 만든 팰린드롬 분할의 수이다.

 

예를 들며 확인해보자

BBCDDECAECBDABAD 와 같은 입력이 들어왔다 가정해보자

(* 해당 문자열의 길이는 16이다.)

 

가장 마지막 문자인 D 가 들어오기 전까지의 최소 팰린드롬 분할의 수를 알고 있다고 가정하고 이를 F[i] 에 저장했다고 하자.(* i는 문자의 순서로 F[15] 는 15번째 문자까지 들어왔을 때의 최소 팰린드롬 분할의 수이다.)

 

16번째 문자인 D가 들어왔다.

입력받은 D를 통해 만들 수 있는 팰린드롬은 12번째 문자부터 16번째 문자까지 {D, A, B, A, D} 이다.

이때 팰린드롬 분할의 수는

F[11] + 1 일 것이다.

 

다음과 같은 방식으로 가능한 팰린드롬 분할의 수들 중 가장 작은 값을 F[16]에 저장하면 된다.

 

다른 예를 들어보자

ABBAB 와 같은 입력이 들어왔다 가정해보자

그리고 입력은 5번째 문자인 B이다.

 

입력받은 B를 통해 만들 수 있는 팰린드롬은 3번째 문자인 B를 포함하는 팰린드롬, {B, A, B} 이다.

그렇다면 이때 만들어지는 팰린드롬 분할의 수는 F[2] + 1 이다.

 

이때 F[2] 는 2이다.(* AB 를 통해 만들 수 있는 최소 팰린드롬 분할의 수는 2이다.)

따라서 만들어지는 분할의 수는 3이다.

 

하지만 입력받은 팰린드롬을 통해 팰린드롬을 만들지 않은 경우의 분할 수는 2이다.(* {A, B, B, A}, {B})

따라서 3은 2보다 작으니 그냥 F[5] 는 2가 된다.

 

코드

 

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

public class Main {

    public static boolean[][] P;
    public static int[] F;
    public static String input;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        input = br.readLine();

        // P[i][j] 는 i 번째 문자부터 j 번째 문자까지의 문자열이 팰린드롬인지 아닌지를 알 수 있는 배열이다.
        P = new boolean[input.length() + 1][input.length() + 1];
        // F[i] 는 i 번째 문자까지의 최소 팰린드롬 분할의 수이다.
        // 그렇다면 우리가 최종적으로 원하는 정답은 F[input.length() - 1] 이다.
        F = new int[input.length() + 1];

        // 길이가 1인 문자는 무조건 팰린드롬이다.
        for(int i=1; i<=input.length(); i++){
            P[i][i] = true;
        }

        // 문자열 길이가 0 인 문자열의 최소 팰린드롬 분할의 개수는 0 이다.
        F[0] = 0;
        // 처음 시작의 최소 팰린드롬 분할의 개수는 1이므로, 1로 초기화해준다.
        F[1] = 1;
        for(int i=2; i<=input.length(); i++){
            // 우선 최소 팰린드롬 분할의 개수는 이전 팰린드롬 분할 개수 + 1 이다.
            // 만약 이보다 작은 수가 나올 수 있다면 바꿔준다.
            int min = F[i-1] + 1;

            for(int j=1; j<i; j++){
                if(input.charAt(j - 1) == input.charAt(i - 1)){
                    // 같은 문자 사이에 팰린드롬이 아에 없거나, 팰린드롬이 존재한다면,
                    if(j + 1 == i || P[j + 1][i - 1]){
                        // 전체를 팰린드롬으로 설정하고
                        P[j][i] = true;
                        // 만들어지는 팰린드롬 분할의 수가 min 보다 작으면 초기화 해준다.
                        min = Math.min(min, F[j - 1] + 1);
                    }
                }
            }
            // min 값은 F 에 저장한다.
            F[i] = min;
        }
        System.out.println(F[input.length()]);
    }
}

 

배움

 

분할정복, 구현 방법을 생각하기 힘들 땐, 억지로 DP, 분할정복을 생각해보자.

저장, 메모라이즈, 그냥 배열을 통해 저장하자.