(JAVA) 백준 1509번 : 팰린드롬 분할

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

1509번: 팰린드롬 분할

 

 

 

팰린드롬 문제 중 꽤 어려운 문제이다.

 

*** 팰린드롬 유사 문제

https://maivve.tistory.com/29

(JAVA) 백준 10942번 : 팰린드롬?

https://maivve.tistory.com/28

(JAVA) 백준 9933번 : 민균이의 비밀번호

 

 

팰린드롬이란

앞뒤가 똑같은 전화번호 단어 이다.

즉, 앞에서부터 보나 뒤에서부터 보나 똑같은 단어라는 뜻이다.

 

1 또는 121 또는 1221 이 팰린드롬에 해당한다.

 

 

단어 길이가 1인 경우에는 무조건 팰린드롬이고,

단어 길이가 2인 경우에는 두 문자가 같아야지 팰린드롬이고,

단어 길이가 3 이상인 경우에는

 1) 양 끝의 두 문자가 같고, 

 2) 양 끝의 두 문자를 제외하고 안에 있는 단어가 팰린드롬이면

팰린드롬이다.

 

 

그런데 문제는

 

해당 문자열 중 팰린드롬 들로 분리했을 때

그 개수가 가장 작은 값을 찾는 것이다.

 

 

 

 

그렇기 때문에 DP(동적 프로그래밍)을 사용해서 최소값을 찾아내야 한다.

 

위 규칙을 가진 별도의 함수를 통해

 

2차원 boolean 배열에 팰린드롬 여부를 T/F로 저장한다.

 

 

 

 

 

핵심

---

boolean[y][x] : y ~ x 인덱스 내 문자열의 팰린드롬 여부

 

DP[i] : 0(시작) ~ i 까지의 문자들로 이루어진 문자열이 가지는 팰린드롬 개수의 최소값.

 

 

*** 중요

DP[i] = Math.min(DP[i], DP[j - 1] + 1)

   -> i는 1(첫 번째 문자 인덱스) ~ i번째 문자 인덱스 까지의 문자열을 나타냄. i 는 최대 n까지 가능

   -> j 또한 1(첫 번째 문자 인덱스) ~ i번째 문자 인덱스 까지의 문자열을 나타냄. 이 때, j는 항상 최대 i까지 가능

 

이를 보면

n개의 문자를 가진 문자열이 존재할 때

 

j <= i 이고,

i <= n 이다.

 

그래서 2중 for문으로 i와 j를 돌리는데,

boolean[y][x](= 팰린드롬 여부) 를 사용해서 j ~ i 사이 문자열은 팰린드롬인지 아닌지 판단해서

 

팰린드롬인 경우만 놓고 DP를 얻는다.

 

 

 

boolean[j][i] 가 true인 경우에는

 

 

j 인덱스부터 i 인덱스의 문자열의 팰린드롬 최소 개수는 항상 1이므로

 

1 인덱스부터 i 인덱스의 문자열의 기존 팰린드롬 최소 개수보다

 

1 ~ j - 1 인덱스의 문자열의 팰린드롬 최소 개수 + 1 보다 작다면 DP[i] 값을 이 값으로 갱신한다.

*** +1을 하는 이유는 문자 하나가 추가되었기 때문에, 문자 하나는 팰린드롬 1개라고 볼 수 있기 때문이다.

 

 

 

설명이 조금 부족한 것 같습니다..ㅠㅠㅠ

 

남은 부분은 소스코드를 참고해주시면 감사하겠습니다!

 

질문도 받아욥!!

 

 

 

항상 방문해주신 분들에게 감사드립니다 :)

 

 

소스코드

---

 

	import java.io.BufferedReader;
	import java.io.IOException;
	import java.io.InputStreamReader;
	// 백준 1509번 : 팰린드롬 분할
	// 동적 프로그래밍 문제
	public class p1509 {
	static String str;
	static char[] strCharArr;
	static boolean[][] palindromes;
	static int[] dp;
	public static void main(String args[]) throws IOException {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	str = br.readLine();
	strCharArr = str.toCharArray(); // 사용 인덱스 : 0 ~ n - 1
	int n = str.length();
	palindromes = new boolean[n + 1][n + 1]; // 사용 인덱스 : 1 ~ n
	dp = new int[n + 1]; // 사용 인덱스 : 1 ~ n
	// 팰린드롬 설정
	setPalindromes(n);
	palindrome(n);
	System.out.println(dp[n]);
	}
	// 팰린드롬
	// DP[i] => Math.min(DP[i], DP[j - 1] + 1)
	// DP[i] => 0 ~ i - 1 번째까지의 문자들 중 팰린드롬 분할 최소 개수
	// j ~ i 인덱스까지 문자들의 분할 최소 개수 : DP
	static void palindrome(int n) {
	for(int i = 1; i <= n; i++) {
	for(int j = 1; j <= i; j++) {
	if(palindromes[j][i]) {
	// 여기서 dp[i] == 0 인 경우에는 아직 해당 문자열을 탐색한 경우가 없다는 뜻으로 초기 설정이 필요하다.
	if(dp[i] > dp[j - 1] + 1 || dp[i] == 0) {
	dp[i] = dp[j - 1] + 1;
	}
	}
	}
	}
	}
	// DP를 활용한 풀이 방법
	private static void setPalindromes(int n) {
	for(int i = 1; i <= n; i++) {
	// S ~ E의 길이가 1일 때(즉, 한 개의 수만 선택했을 때) 무조건 팰린드롬
	palindromes[i][i] = true;
	// S ~ E의 길이가 2일 때(즉, 두 개의 수만 선택했을 때)
	if(i < n) {
	if(strCharArr[i - 1] == strCharArr[i]) {
	palindromes[i][i + 1] = true;
	palindromes[i + 1][i] = true;
	}
	}
	}
	// S ~ E의 길이가 3 이상일 때
	// 1) 양 끝의 숫자가 같고, 2) 남은 안의 숫자들이 팰린드롬이면 이 길이의 숫자들도 팰린드롬이다.
	for(int i = 3; i <= n; i++) { // i는 S ~ E의 길이. 최소가 3이므로 3부터 시작. = 끝 인덱스
	for(int j = 1; j < n - i + 1; j++) { // i 만큼의 길이를 보고 팰린드롬을 찾기 위한 시작 인덱스.
	int k = j + i - 1;
	if(strCharArr[j - 1] == strCharArr[k - 1]) { // 1)의 조건.
	if(palindromes[j + 1][k - 1]) { // 2)의 조건.
	palindromes[j][k] = true;
	palindromes[k][j] = true;
	}
	}
	}
	}
	}
	}

view raw p1509.java hosted with ❤ by GitHub