[백준 스터디 11주차] 1509번 팰린드롬 분할 골드1 - 자바(JAVA) / 조금 어려운 DP

📑 문제

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

1509번: 팰린드롬 분할

문제

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

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

입력

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

출력

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

 

 

 

 

 

 

 

 

✒️ 풀이

 이 문제는 정말 어려웠다.. (https://lotuslee.tistory.com/6) 이 링크의 풀이를 보고 겨우 이해했다.

 어려운 DP 문제라고 할 수 있다!

💡 특정 문자열의 i번째 위치가 있을 때, 0번째부터 i번째 사이의 j를 두고 j부터 i까지가 팰린드롬인지 확인한다.

 만약 팰린드롬이라면, dp[i]는 현재 저장되어있는 팰린드롬 개수(dp[i])와 dp[j-1]+1 중 작은 값이 될 것이다. dp[j-1]+1에서 1이 뜻하는 것이 바로 j부터 i까지가 팰린드롬이라는 것이다.

 

 1. 모든 부분 문자열에 대하여 팰린드롬을 확인한다 (checkPalindrome) 

 2. 1~i번째까지의 문자열에 대하여, 부분 팰린드롬을 확인한다.

 3. 부분 팰린드롬의 경우, 1과 i 사이의 값 j에 대하여, j~i가 팰린드롬이면 하나의 문자열로 보고, dp[j-1]에 1을 더해준 값을 기존의 값과 비교하여 더 작은 수로 업데이트하는 것이다. 

 

 

 

 

 

 

 

💻 소스코드: 자바(Java)

// https://lotuslee.tistory.com/6
public class Main_백준_1509_팰린드롬분할_골드I {

	static int N;
	static int[] dp;
	static boolean[][] palindrome;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String str = br.readLine();
		N = str.length();
		str = "."+str;
		palindrome = new boolean[N+1][N+1];
		dp = new int[N+1]; // 1~i번째까지의 문자열에서 팰린드롬의 개수를 저장
		
        // str의 부분문자열에 대한 팰린드롬을 모두 체크한다.
		checkPalindrome(str);
		
		Arrays.fill(dp, Integer.MAX_VALUE);
		dp[0] = 0;
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= i; j++) {
				if(palindrome[j][i]) dp[i]=Math.min(dp[i], dp[j-1]+1);
			}
		}
		System.out.println(dp[N]);
	}//end of main
	
	private static void checkPalindrome(String str) {
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= i; j++) {
				boolean flag = true;
				int from = j;
				int to = i;
				while(from<=to) {
					if(str.charAt(from++) != str.charAt(to--)) {
						flag = false;
						break;
					}
				}
				if(flag) palindrome[j][i] = true;
			}
		}
	}
}//end of class

 

 

 

 

 

 

 

 

 

 

 

💎 💎 💎

 

 

Ｐｏｓｔｅｄ Ｂｙ ＳＡＹ

𝘛𝘩𝘢𝘯𝘬𝘴 𝘧𝘰𝘳 𝘳𝘦𝘢𝘥𝘪𝘯𝘨