boj 1509: 팰린드롬 분할

어떤 문자열을 팰린드롬으로 분할하는데, 분할 개수의 최솟값을 구하는 문제이다.

 

일단 팰린드롬의 연속이 되어야 하고,

정답의 최댓값은 N이 될 것이다. (길이가 1인 문자열은 항상 팰린드롬이니까)

 

DP[i]: str[i]까지 문자열까지의 팰린드롬 분할 갯수의 최솟값

DP[i] = Math.min(D[j-1]) + 1(단, j ~ i까지는 팰린드롬)

=> 시간복잡도는 DP를 채워야 하는 갯수 N * j를 찾는 시간 N * i~ j가 팰린드롬인지 아닌지 찾을 때 O(1): O(N^2)

 

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

public class Main {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;

		String str = br.readLine();
		char[] arr = str.toCharArray();

		int n = str.length();
		int dp[][] = calcPalindrome(arr, n);
		int ans = calcDividedPalindrome(dp, n);
		bw.write(String.valueOf(ans));
		bw.flush();
		bw.close();
	}

	public static int[][] calcPalindrome(char arr[], int n) {
		int dp[][] = new int[n + 1][n + 1];

		// 길이가 1일 때
		for (int i = 1; i <= n; i++) {
			dp[i][i] = 1;
		}

		// 길이가 2일 때
		for (int i = 1; i <= n - 1; i++) {
			if (arr[i - 1] == arr[i]) {
				dp[i][i + 1] = 1;
			}
		}

		// 길이가 3 이상
		for (int i = 3; i <= n; i++) {
			for (int j = 1; j <= n - i + 1; j++) {
				int k = j + i - 1;
				if (arr[j - 1] == arr[k - 1] && dp[j + 1][k - 1] == 1) {
					dp[j][k] = 1;
				}
			}
		}

		return dp;
	}

	public static int calcDividedPalindrome(int dp[][], int n) {
		int maxDivided[] = new int[n + 1];

		for (int i = 1; i <= n; i++) {
			maxDivided[i] = -1;
			for (int j = 1; j <= i; j++) {
				if (dp[j][i] == 1) {
					if (maxDivided[i] == -1 || maxDivided[i] > maxDivided[j - 1] + 1) {
						maxDivided[i] = maxDivided[j - 1] + 1;
					}
				}
			}
		}

		return maxDivided[n];
	}
}

 

BufferedWriter is a method that flush the buffer and write the characters directly to the underlying stream.

따라서 int형의 ans를 바로 bw.write하게 되면 char형으로 output이 나온다.

따라서 String형으로 바꿔준 뒤 쓰도록 한다.