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

문제

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

1509번: 팰린드롬 분할

 

풀이

일단 이전 단계인 문제 팰린드롬?을 풀고 오자.

 

이전 문제에서 우리는 start에서 end까지 팰린드롬을 이루는지의 여부를 is_palin[start][end]  저장해 문제를 해결하였다.

이번 문제에서도 해당 저장 값을 그대로 이용하자.

 

첫 글자(1)에서 현재 위치 (i)까지의 팰리드롬 개수의 최솟값을 dp[i]에 저장하자.

 

 i 번째 글자까지가 팰린드롬이지의 여부는 is_palin[1~i][i]를 확인해보면 된다.

 

is_palin[j+1][i]이 true인 경우

  j+1~i까지를 하나의 팰린드롬으로 묶어 1개의 분할을 얻는다.

 

그리고 1~j까지의 팰리드롬 분할 개수의 최솟값을 저장하는 dp[j]값을 1과 더해

 (j+1,i)를 팰린드롬 으로 묶을 때의 최솟값을 dp[j] +1로 얻을 수 있다.

 

이제 j를 0~i-1까지 순회하며 얻은 가장 작을 값이 dp[i]의 값이 된다.

따라서 dp[i] = min(dp[i], dp[j+1]+1) 이다.

 

참고로 문자열을 인덱스 1부터 시작하도록 변환하여

dp[0] = 0의 값을 미리 넣어두면

dp[2] = min(dp[2], dp[0]+1)과 같이 1~2를 하나의 팰린드롬으로 묶었을 때 이전의 글자가 더 없기 때문에, 계산이 용이해진다.

 

코드

	#include <iostream>
	#include<string>
	#include<string.h>
	using namespace std;
	string arr;
	bool is_palin[2501][2501];
	int dp[2501];
	int main() {
	ios_base :: sync_with_stdio(false);
	cin>>arr;
	arr = "+" + arr;
	memset(is_palin, false, sizeof(is_palin));
	for(int i=0; i<arr.length() ; ++i)
	is_palin[i][i] = true;
	for(int end =2; end<arr.length() ; ++end)
	for(int start = 1 ; start<end ; ++start)
	if(arr[start] == arr[end]){
	if(end - start >=2)
	is_palin[start][end] = is_palin[start+1][end-1];
	else
	is_palin[start][end] = true;
	}
	dp[0] = 0;
	dp[1] = 1;
	int min_palin;
	for(int i =2; i<arr.length() ; ++i){
	dp[i] = 2500;
	for(int j = 0 ; j<i ; ++j)
	if(is_palin[j+1][i])
	dp[i] = min(dp[i],dp[j] + 1);
	}
	cout<<dp[arr.length()-1]<<'\n';
	return 0;
	}

view raw [BaekJoon]_1509_팰린드롬 분할.cpp hosted with ❤ by GitHub