1509 팰린드롬 분할
알고리즘(Manacher’s Algorithm, DP)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
1. 2차원 bool 형 배열 palindrome에 모든 팰린드롬을 저장.
-> palindrome[i][j] 엔 시작이 i이고 끝이 j인 문자열이 팰린드롬인지 아닌지 저장돼있음
-> 구하는 법은 처음부터 i = 0~length, j = i~length; 로 가면서 팰린드롬인지 확인하고,
팰린드롬이면 Manacher’s Algorithm 으로 그 사이 팰린드롬을 전부 표시
아니면 그냥 넘어간다
-> 팰린드롬일경우 그 사이는 전부 표시했으니, 이중for문 진행하면서 palindrome[i][j]이 true면 그냥 넘어가면 된다.
2. 저장한 palindrome을 바탕으로 바텀업 DP 시행
-> DP[length] : 각 시작점이 x일때 이후 최소의 분할수를 기록한 것.
-> DP함수 처음 호출할 때 시작을 0으로 하고, 끝점을 0에서 length까지 검사하며 각 끝점에 대해 팰린드롬이면 start + 1를 주며 아래로 내려간다.
-> 그리고 start가 length와 같아지면 0을 반환하며 1씩 증가하며 올라간다.
-> 이때 각 시작점에선 모든 끝점에 대해 반환값이 최소인 것을 result에 기록하고, 모든 끝점에 대한 검사가 끝나면 DP[start]에 result를 기록하고 반환한다.
바텀업으로 재귀 DP 사용하니 느림
다른방법
1
2
3
4
5
-> 해보니 시간은 비슷하다. 그냥 다른 DP 방식도 있는걸로 알고 넘어가자
1. 반복문으로, i : 1~length / j : i+1~length 를 검사
2. 이전에 저장된 값이 있으면, DP[i-1] + 1하고 비교했을 때 더 크면 그걸로 업데이트 아니면 그냥 넘어가기
3. 저장된값이 없으면 DP[i-1] + 1 저장
4. 각 시작부분은 시작 시 위 2~3을 한다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
for (int i = 1; i <= length; i++){
if ((DP[i] != 0 && DP[i] >DP[i - 1] + 1) || DP[i] == 0)
DP[i] = DP[i - 1] + 1;
for (int j = i + 1; j <= length; j++){
if (Dp[i][j] != 0)
{
if ((DP[j] != 0 && DP[j] >DP[i-1] + 1) || DP[j] == 0)
DP[j] = DP[i - 1] + 1;
}
}
}
코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include <iostream>
#include <string>
#define MAX_LENGTH 2500
using namespace std;
//2차원 배열로 모든 팰린드롬 저장
//첫번째 줄에 팰린드롬인것을 하나씩 넣음
//그리고 오른쪽 아래로 내려가며 가능한 것을 최대한 넣자.
//ex) map[0][0] 은 무조건 팰린드롬이니 고름 -> map[1][1]에서 가장가까운 팰린드롬 고름 map[1][1] -> map[2][2] -> ..... 총길이 2500, -> map[1][2] ...map[1][3].. 이렇게 진행?
//위처럼 진행할 경우 2500*2500 + 2499*2499 + ... 총 26억 계산 -> 시간초과
//가장가까운이 아닌, 가장 먼곳부터 골라보자. map[0][n] ... 그리고 길이가 이미고른 길이보다 길면 중간종료 하는 식으로?
//하지만 최악의 경우 또 26억이 됨
//DP = 위 계산을 바텀업방식으로 하여 DP[x] 에 길이를 저장하는 방식으로 해보자
int length, DP[MAX_LENGTH];
char input[MAX_LENGTH];
bool palindrome[MAX_LENGTH][MAX_LENGTH];
void makePalindrome();
bool isPalindrome(int start, int end);
void recordPalindrome(int start, int end);
int getMinSplit(int start);
int min(int a, int b) {
return a < b ? a : b;
}
int main() {
string tempInput;
cin >> tempInput;
length = tempInput.size();
for (int i = 0; i < tempInput.size(); i++)
input[i] = tempInput[i];
makePalindrome();
cout << getMinSplit(0);
}
void makePalindrome() {
for (int i = 0; i < length; i++) {
for (int j = length - 1; j >= i; j--) {
if (palindrome[i][j] != 0)
continue;
if (isPalindrome(i, j))
recordPalindrome(i, j);
else
palindrome[i][j] = 0;
}
}
}
bool isPalindrome(int start, int end) {
for (; start < end; start++, end--)
if (input[start] != input[end])
return false;
return true;
}
void recordPalindrome(int start, int end) {
for (; start <= end; start++, end--)
palindrome[start][end] = 1;
}
int getMinSplit(int start) {
if (start == length)
return 0;
if (DP[start])
return DP[start];
int result = 200000000;
for (int i = length-1; i >= start; i--)
if (palindrome[start][i])
result = min(result, getMinSplit(i + 1) + 1);
return DP[start] = result;
}