BOJ_1509_팰린드롬 분할(Java)

[Gold I] 팰린드롬 분할 - 1509

문제 링크

성능 요약

메모리: 46856 KB, 시간: 188 ms

분류

다이나믹 프로그래밍

제출 일자

2024년 9월 2일 13:18:03

문제 설명

세준이는 어떤 문자열을 팰린드롬으로 분할하려고 한다. 예를 들어, ABACABA를 팰린드롬으로 분할하면, {A, B, A, C, A, B, A}, {A, BACAB, A}, {ABA, C, ABA}, {ABACABA}등이 있다.

분할의 개수의 최솟값을 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 문자열이 주어진다. 이 문자열은 알파벳 대문자로만 이루어져 있고, 최대 길이는 2,500이다.

출력

첫째 줄에 팰린드롬 분할의 개수의 최솟값을 출력한다.

문제풀이

코드

/**
 * Author : nowalex322, Kim HyeonJae( KR )
 */

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

public class Main {
	static BufferedReader br;
	static StringTokenizer st;
	public static void main(String[] args) throws IOException {
		br = new  BufferedReader(new InputStreamReader(System.in));
//		br = new BufferedReader(new InputStreamReader(new FileInputStream("input.txt")));
		
		String str = br.readLine();
		int len = str.length();
		char[] arr = str.toCharArray();
		
        boolean[][] isPalindrome = new boolean[len][len];
		int[][] dp = new int[len][len];
		
        for (int i = 0; i < len; i++) {
            isPalindrome[i][i] = true;
            if (i >0 && arr[i-1] == arr[i]) isPalindrome[i-1][i] = true;
        }
        for(int i=3; i<=len; i++) {
        	for(int start=0; start<=len-i; start++) {
        		int end = start+i-1; // 끝 인덱스
        		if(arr[start] == arr[end] && isPalindrome[start+1][end-1]) isPalindrome[start][end] = true;
        	}
        }
		
		for(int i=0; i<len; i++) {
			if(isPalindrome[0][i]) dp[0][i] = 1;
			else {
				dp[0][i] = i+1; // 최악의 경우로 세팅
				for(int j=0; j<i; j++) {
					if(isPalindrome[j+1][i]) dp[0][i] = Math.min(dp[0][i],  dp[0][j] + 1);
				}
			}
		}
//		for(int i=0; i<len; i++) {
//			for(int j=0; j<len; j++) {
//				System.out.print(dp[i][j] + " ");
//			}
//			System.out.println();
//		}
		System.out.println(dp[0][len-1]);
	}
}