백준, boj) 1509. 팰린드롬 분할 ( C / C++)

1. 문제 링크

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

1509번: 팰린드롬 분할

2. 문제 개요

어떤 문자열을 팰린드롬으로 분할하려고 한다. 분할의 개수의 최솟값을 구하시오, 즉 원소의 개수가 최소가 되도록 해야 함.

3. 문제 힌트

처음에 분할의 최솟값이라고 하길래 분할하면 분할했지 분할의 최솟값은 뭐지?라고 생각했다. 질문란 이런 곳을 찾아보니 분할의 경우의 수가 아니고 분할했을 때 원소 개수의 최솟값을 찾는 것이었다.

 

(1) 팰린드롬 찾기. 잘 생각해보자 바깥쪽부터 안쪽으로 한 칸씩..

(2) 분할을 찾아야 하는데 dp를 사용해보자.

dp[index] : index에서 시작해서 끝까지의 분할의 개수의 최솟값으로 둬보자.

 

4. 문제 풀기

우선, 모든 분할은 팰린드롬이다. 즉 원소를 잘라낼 때 팰린드롬이 아니면 잘라낼 수 없다. 그러니까 어디서 어디까지가 팰린드롬인지 알아야 할 필요가 있다.

처음에 While반복문으로 구하고 AC를 받았다. 그리고 다른 사람의 풀이를 봤는데 재귀로 구현한 사람이 있었다. 정말 한눈에 이해가 되고 코드가 섹시했다... 충격받아서 바로 외워버린 (코드가 간단하고 깔끔한 것이지 while반복문으로 구해도 손해?는 없다. 오히려 재귀가 아니기 때문에 빠르면 더 빨랐지. 깔끔한 것의 차이)

 

그다음은 팰린드롬인 부분을 잘라가면서 뒤로 나아가는 것이다.

dp[index]는 index부터 시작해서 문장의 끝까지 분할의 개수의 최솟값으로 두었다.

 

예를 ABACABA로 둬보자. ( 문제의 내용과 같은 예 )

dp(0)이 정답이 될 것이다. 분할을 계속 이어 나가보자.

현재 index가 0이고, 다음 팰린드롬은 2번 index이다.

(지금 cur == 0 임)

ans = min(ans, dp(3) + 1)이 될 것이다.

왜냐하면 0~2까지 1개의 팰린드롬이 되었기 때문에 +1을 해주는 것이다. 나머지 부분은 3~6까지의 최솟값을 알면 된다. 

이런 식으로 팰린드롬인 부분을 기준으로 잘라나가면 피보나치처럼 재귀 함수가 뻗어 나갈 것이다.

메모이제이션을 해주자.

dp(7) 즉, 문장의 길이만큼 도달하면 끝까지 도달한 것이기 때문에 0을 리턴해주자.

그러니까 결국 모든 경우의 수만큼 잘라볼 건데 메모이제이션을 사용해서 실행시간을 줄이는 것이다.

 

 

그리고 인접리스트를 사용해서 반복의 수를 줄여봤는데 그냥 인접행렬로 하는게 더 빨랐다.

5. 코드

#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;

string s;
int dp_arr[2500][2500];
int dp_table[2500];
int len;

int dp(int cur)
{
	if (cur >= len)	return 0;

	int &cache = dp_table[cur];
	if (cache != -1)	return cache;

	int ans = 987654321;
	for (int i = 0; i < len; ++i) {
		if (i < cur)continue;
		if (dp_arr[cur][i] == 0)	continue;
		ans = min(ans, dp(i + 1) + 1);
	}
	return cache = ans;
}
int get_pal(int l, int r) 
{
	int &cache = dp_arr[l][r];
	if (cache != -1)	return cache;
	if (l >= r)	return cache = 1;
	if (s[l] != s[r])	return cache = 0;
	
	return cache = get_pal(l + 1, r - 1);
}
int main(void)
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	cin >> s;
	memset(dp_arr, -1, sizeof(dp_arr));
	memset(dp_table, -1, sizeof(dp_table));
	len = s.length();

	for (int i = 0; i < len; ++i) 
		for (int j = i; j < len; ++j) 
			get_pal(i, j);

	cout << dp(0);
	return 0;
}

6. 결과 사진

지적, 댓글 언제나 환영입니다~