[C++] 백준(BOJ) - 1509 : 팰린드롬 분할

25 Apr 2024 in Develop on C++, Algorithm

인프런에 있는 큰돌님의 강의 10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트를 듣고 정리한 필기입니다.

• 문제
• 입력
• 출력
• 알고리즘
• 풀이
• 코드
• 평가

문제

BOJ - 1509 : 팰린드롬 분할(링크)

세준이는 어떤 문자열을 팰린드롬으로 분할하려고 한다. 예를 들어, ABACABA를 팰린드롬으로 분할하면, {A, B, A, C, A, B, A}, {A, BACAB, A}, {ABA, C, ABA}, {ABACABA}등이 있다.

분할의 개수의 최솟값을 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 문자열이 주어진다. 이 문자열은 알파벳 대문자로만 이루어져 있고, 최대 길이는 2,500이다.

출력

첫째 줄에 팰린드롬 분할의 개수의 최솟값을 출력한다.

알고리즘

1. DP (Bottom Up)

풀이

• dp를 활용해 점화식을 만들기
  • dp[j][size] : j부터 size만큼 팰린드롬일 경우 dp에 1 대입
• 분할의 최소개수를 찾기위한 DP배열 추가로 선언

1. 자기 자신은 1만큼의 사이즈를 가지는 팰린드롬이다
2. 바로 옆의 수가 같으면 2만큼의 사이즈를 가지는 팰린드롬이다
3. 가운데에 문자열이 팰린드롬이고 그 팰린드롬의 앞뒤 문자가 같으면 팰린드롬이다

코드

// BOJ - 1509 : 팰린드롬 분할
#include <bits/stdc++.h>
using namespace std;
const int INF = 2147000000;
int dp[2504][2504]; // 시작지점과 팰린드롬의 사이즈를 상태값으로 가짐
int dp2[2504];		// 분할의 최소개수를 찾기위한 dp배열
string str;

int go(int here)
{
	if (here == str.size()) return 0;
	if (dp2[here] != INF) return dp2[here];
	int& res = dp2[here];
	for (int i = 1; i + here <= str.size(); i++)
	{
		if (dp[here][i]) res = min(res, go(here + i) + 1);
	}
	// cout << here << " : " << res << '\n';
	return res;
}

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

	cin >> str;

	for (int i = 0; i < str.size(); i++) dp[i][1] = 1;
	for (int i = 0; i < str.size() - 1; i++)
	{
		if (str[i] == str[i + 1]) dp[i][2] = 1;
	}

	for (int _size = 3; _size <= str.size(); _size++)
	{
		for (int j = 0; j + _size <= str.size(); j++)
		{
			if (str[j] == str[j + _size - 1] && dp[j + 1][_size - 2]) dp[j][_size] = 1;
		}
	}
	fill(dp2, dp2 + 2504, INF);
	cout << go(0) << '\n';

	return 0;
}

평가

• DP BottomUp의 경우 전처리가 필요
• 시작점과 사이즈를 상태값으로 정의한다는 아이디어