[BAEKJOON] 1509번 팰린드롬 분할

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

1509번: 팰린드롬 분할

 

문제조건

1. 어떤 문자열을 팰린드롬으로 분할한다.
2. 분할된 수의 최솟값을 출력

팰린드롬이란?

 

어떤 문자가 있을때, 거꾸로 뒤집어서 읽어도 똑같은 문자를 의미한다.

ex) 기러기 ☞ 기러기(O)

cf) 거북이 ☞ 이북거(X)

 

이 문제에서 핵심은 문자가 입력으로 들어왔을때, 문자열안에서의 모든 경우의수를 탐색해서 팰린드롬인지 각각 파악해야하는데, 팰린드롬인지 아닌지 어떻게 판단하냐는거다. 일단 단순하게 제일 기본적인 조건은 맨 앞 문자와 맨 끝 문자는 항상 같아야 팰린드롬이다. 그리고 문자열 길이가 1 이라면 당연히 팰린드롬이다. 그리고 2일 경우에는 두 문자가 같은 문자여야만 팰린드롬이다. 이제 3개일때는 어떻게 될까? 3개일때는 이전에 구했던 문자열의 길이가 1, 2일때의 정보를 활용해서 구할 수 있다. 시작과 끝의 문자가 같고, 그 사이가 팰린드롬인지 파악해주기만 하면된다.

이것까지만 파악했다면 최소로 분할되는 걸 구하는 과정은 쉽다.

dp[n]이라는 배열을 n까지 최소로 분할되는 개수라고 하면, 완전탐색으로 최솟값을 구해주면 된다.

• if (palin[j][i]) dp[i] = min(dp[i], dp[j - 1] + 1);

위 코드는 i까지 최소개수와, 팰린드롬이라고 j-1 번째까지 최소개수와 판별된 j번째부터 i번째까지를 한번 더한 것을 비교해서 작은값으로 계속해서 갱신해준다. 결국 dp[n-1]에는 전체 문자열에서 최소로 분할 할수있는 팰린드롬의 개수가 나올것이다.

#include <iostream>
#include <vector>
#define MAX 2501
using namespace std;

string s;
int dp[MAX];
bool palin[MAX][MAX];
int main(){
	cin >> s;
	for (int i = 0; i < s.length(); i++) {
		palin[i][i] = true;
		if (i < s.length() && s[i] == s[i + 1]) palin[i][i + 1] = true;
	}

	//3개 이상 팰린드롬일 경우
	for (int i = 3; i <= s.length(); i++) {
		for (int j = 0; j <= s.length() - i; j++) {
			int k = i + j - 1;
			if (s[j] == s[k] && palin[j + 1][k - 1]) palin[j][k] = true;
		}
	}
	dp[0] = 1;
	for (int i = 1; i < s.length(); i++) {
		dp[i] = MAX;
		for (int j = 0; j <= i; j++) {
			if (palin[j][i]) dp[i] = min(dp[i], dp[j - 1] + 1);
		}
	}
	cout << dp[s.length() - 1];
}