백준1509 팰린드롬 분할

작성일 | In

문제 링크

  • http://icpc.me/1509

사용 알고리즘

  • DP

시간복잡도

  • O(N2)

풀이

이 문제는 두 가지 부분 문제로 나눌 수 있습니다.

  1. 팰린드롬을 빠르게 판별하는 문제
  2. 분할 개수의 최솟값을 구하는 문제

팰린드롬을 빠르게 판별하는 것은 DP로 할 수 있습니다.
[S, E]구간이 팰린드롬인지 판별하는 것은 보통 while문을 사용합니다.
while문 대신 재귀 형태로 구현한 다음에 메모이제이션을 해주면 상태 공간은 총 O(N2)개, 각 상태마다 O(1)에 답을 구할 수 있으므로 O(N2)만에 모든 구간에 대해 팰린드롬인지 판별할 수 있습니다.

분할 개수의 최솟값을 구하는 것도 DP로 할 수 있습니다.
dp[n] = [1, n]구간을 분할하는 최소 개수 라고 정의합시다.
만약 [j, i]구간이 팰린드롬이라면, [1, j-1]까지 잘 분할하고, [j, i]를 한 덩어리로 만들어주면 됩니다.
그러므로 dp[i] = min(dp[j-1] + 1)으로 답을 구해줄 수 있습니다. (단, j <= i and [j, i]는 팰린드롬)

전체 코드

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
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
using namespace std;

typedef long long ll;
typedef pair<ll, ll> p;

ll dp[2525][2525];
ll dp2[2525];
string s;
int n;

int isPal(int st, int ed){
	ll &res = dp[st][ed];
	if(res != -1) return res;
	if(st >= ed) return 1;
	if(s[st] != s[ed]) return res = 0;
	return res = isPal(st+1, ed-1);
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> s; n = s.size(); s = '#' + s;
	memset(dp, -1, sizeof dp);

	memset(dp2, 0x3f, sizeof dp2);
	dp2[0] = 0;
	for(int i=1; i<=n; i++){
		dp2[i] = dp2[i-1] + 1;
		for(int j=1; j<i; j++){
			if(!isPal(j, i)) continue;
			dp2[i] = min(dp2[i], dp2[j-1] + 1);
		}
	}
	cout << dp2[n];
}