(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개라고 볼 수 있기 때문이다.

 

 

 

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

 

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

 

질문도 받아욥!!

 

 

 

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

 

 

소스코드

---