백준 / 1509 팰린드롬 분할 C++

www.acmicpc.net/problem/1509

1509번: 팰린드롬 분할

주어진 문자열을 팰린드롬으로 나누는 경우 중 분할된 개수의 최솟값을 구하는 문제입니다.

ABACABA의 경우 문제에 나와있듯이 {A,B,A,C,A,B,A}, {A,BACAB,A}, {ABA,C,ABA}, {ABACABA} 와 같이 나타낼 수 있고 이 때는 분할의 최소 개수가 1입니다.

 

풀이 : dp를 이용해 풀었습니다.

 

1. 주어진 문자열에 대해 i번째 문자부터 j번째 문자가 팰린드롬인지 확인합니다. 팰린드롬이면 dp[ i ][ j ] = true, 아니면 false 입니다.

 

i > j인 경우는 안 해도 되므로 2500+2499+...+1 = O(n^2) 임을 알 수 있습니다. 최대 길이가 2500인 string에 대한 연산이므로 대략적으로 팰린드롬이 되는지 체크 (is_pelindrom)를 1250 번 돈다고 계산했을 때 시간초과에 약간의 우려가 있습니다. (제한시간 2초)

 

2. dp[i] : 첫번째 문자부터 i번째 문자까지 팰린드롬 분할의 최소 개수

 

계산의 편의를 위해 string의 맨 앞에 '.'을 붙혔습니다. (첫번째 알파벳 = index 1)

또한 dp[0]=0으로 잡고, dp[1]=1 입니다.

이제 dp[i] = min(dp[i], dp[ j-1 ]+1) 임을 알 수 있습니다. j는 i부터 1까지 돌고, pelin[ j ][ i ]가 true이면 j 부터 i 번째 문자열은 팰린드롬이므로 dp[ j - 1 ] + 1을 해주면 됩니다.

( j가 첫번째 문자에 해당될 수 있으므로 dp[-1]을 정의하기 위해 string의 맨 앞에 '.'을 붙혔습니다.)

 

여기서 최대 2500*2500 번 연산을 한다고 잡으면 (실제로는 n(n+1)/2) 600만번 연산이므로 제한시간 2초에 통과합니다. i 부터 j까지가 팰린드롬인지 확인하는 과정에서 겹치는 부분이 있어서 시간을 줄이고 싶다면 여기를 처리하면 됩니다.

 

코드는 다음과 같습니다.

#include<iostream>
#include<algorithm>
#include<string>

using namespace std;

string s;
int len; // s의 길이, '.'포함
bool pelin[2501][2501]; // pelin[x][y] : index가 x부터 y까지가 펠린드롬이면 true, 아니면 false
int dp[2501]; // dp[i] : i번째까지 펠린드롬 최소 개수
// dp[i] = min(dp[i], dp[j-1]+1) 
// j : i부터 1까지 돌면서 펠린드롬이면 직전값+1로 업데이트

void init()
{
	cin >> s;
	s.insert(0, "."); 
	// 맨 앞에 '.' 추가 : 맨 처음문자까지 돌았을 때 펠린드롬이면 dp[0]=0으로 생각 
	len = s.size();
	for (int i = 0; i < len; i++) {
		for (int j = 0; j < len; j++) {
			pelin[i][j] = false;
		}
		dp[i] = 987654321;
	}
}

bool is_pelindrom(int start, int last)
{
	int mid = (start + last) / 2; // 가운데값
	int i = 0;
	bool check = true;
	while ((start + i) <= mid) {
		if (s[start + i] != s[last - i]) {
			check = false;
			break;
		}

		i++;
	}
	return check;
}

void make_pelindrom()
{
	for (int i = 1; i < len; i++) {
		for (int j = i; j < len; j++) {
			if (is_pelindrom(i, j))
				pelin[i][j] = true;
		}
	}
}

void calculate_dp()
{
	dp[0] = 0;
	dp[1] = 1;

	for (int i = 2; i < len; i++) {
		for (int j = i; j > 0; j--) {
			if(pelin[j][i])
				dp[i] = min(dp[i], dp[j - 1] + 1);
		}
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	init();
	make_pelindrom();
	calculate_dp();
	cout << dp[len - 1];
}