자바 - 백준 1509 / 팰린드롬 분할

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

골드1

구현 방법

문자열에 대해 모든 팰린드롬을 구하는 방법은 dp[시작문자 위치][끝 문자 위치]를 사용해서 구했다. 

https://kdozlo.tistory.com/53

이제 dp[시작 문자 위치][끝 문자 위치]를 이용하여 팰린드롬 수로 분할의 개수의 최솟값을 구해야 한다. 

처음에 dfs로 하면 되겠다 싶어서 구현했는데 두가지 문제점이 있었다.

첫번째로는 끝에서부터 팰린드롬 수인 경우 그 다음을 카운터 하는 방식으로 구현했는데, 이렇게 했을 때 항상 최적의 최소값이 나오지 않는다. 따라서 그리디하게 풀면 안되고 모든 경우를 따져야 한다.

두번째 문제는 시간복잡도가 너무 높다. 문자열의 최대 길이가 2500인데 심지어 모든 경우를 따지면 2^2500의 복잡도를 가지게 된다.

 

따라서 dfs나 bfs와 같이 완전 탐색 방법을 써버리면 틀리게 된다.

시간복잡도를 낮추기 위해서는 기존에 계산 했던 부분을 다시 하지 않도록 기억하는 방법을 사용하면 된다.

나는 계산 했던 부분을 기억하기 위해 다이내믹 프로그래밍 방법을 사용하기로 했다.

 

구현 로직을 떠올리기 힘들었는데 방식은 다음과 같다. 

answer[현재 문자열 인덱스] = 팰린드롬 수로 분할의 개수의 최솟값의 형태로 dp를 사용한다.

1. 문자열 시작부터 현재 문자열까지가 팰린드롬인지 확인 한다.

2-1. 팰린드롬인 경우 answer[현재 문자열 인덱스] = 1로 주고 끝낸다.

        왜냐하면 현재까지가 팰린드롬 수이기 때문에 더 이상 나눌 필요가 없다.

2-2. 팰린드롬이 아닌경우 현재 문자열까지 최솟값으로 팰린드롬 수 분할을 해야한다. 

        따라서 (0 <= j  < 현재 문자열 인덱스)까지 팰린드롬 수인지 확인하고,

        맞는 경우 answer[현재 문자열 인덱스] = Math.min(answer[현재 문자열 인덱스], answer[j] + 1)로 최솟값을 확인한다.

코드

import java.io.*;

/**
 * 백준 1509
 * 팰린드롬 분할
 * 골드1
 * https://www.acmicpc.net/problem/1509
 */
public class Boj1509 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        char[] s = br.readLine().toCharArray();
        int len = s.length;

        boolean[][] dp = new boolean[len][len];

        for(int i = 0; i < len; i++)
            dp[i][i] = true;

        for(int i = 1; i < len; i++) {
            if(s[i - 1] == s[i])
                dp[i - 1][i] = true;
        }

        for(int l = 2; l < len; l++) {
            for(int i = 0; i < len - l; i++) {
                int j = i + l;
                if(s[i] == s[j] && dp[i + 1][j - 1])
                    dp[i][j] = true;
            }
        }

        int[] answer = new int[len];

        for(int i = 0; i < len; i++) {
            if(dp[0][i]) {
                answer[i] = 1;
            } else {
                answer[i] = 2501;

                for(int j = 0; j < i; j++) {
                    if(dp[j + 1][i]) {
                        answer[i] = Math.min(answer[i], answer[j] + 1);
                    }
                }
            }
        }

        System.out.println(answer[len - 1]);
    }
}