BOJ 1509 - 팰린드롬 분할

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

문제

$dp[i]$ = $i$번째 위치에서 가능한 팰린드롬 분할의 최소 개수

$isPaline[i][j]$ = $i~j$ 가 팰린드롬인지 여부

예제에도 끼워져있지만 AABDBADD 와 같은 경우의 처리때문에 여러 경우를 탐색해야한다. 이것을 분할하는 경우는 아래와 같다.

A - A - B - D - B - A - D - D
A - A - B - D - B - A - DD
A - A - BDB - A - D - D
A - A - BDB - A - DD
A - ABDBA - D - D
A - ABDBA - DD
AA - B - D - B - A - D - D
AA - B - D - B - A - DD
AA - BDB - A - D - D
AA - BDB - A - DD

팰린드롬으로 최대한 묶은 후, 남은 문자열에 대해서 이 작업을 반복한다.

코드

	#include <bits/stdc++.h>
	using namespace std;
	#define INF 987654321
	bool isPaline[2501][2501];
	int dp[2501];
	int solve(int pos){
	if(pos < 0) return 0;
	int& r = dp[pos];
	if(r != -1) return r;
	r = INF;
	for(int i=pos; i>=0; --i){
	if(isPaline[pos][i]){
	r = min(r, 1+solve(i-1));
	}
	}
	return r;
	}
	int main(){
	memset(dp, -1, sizeof(dp));
	char s[2501];
	scanf("%s", s);
	int len=strlen(s);
	for(int i=0; i<len; ++i){
	isPaline[i][i] = true;
	for(int j=0; j<i; ++j){
	if(s[i]==s[j]) isPaline[i][j] = isPaline[i-1][j+1];
	// 짝수인 경우 처리
	if(i-j==1) isPaline[i][j] |= s[i]==s[i-1];
	}
	}
	printf("%d", solve(len-1));
	return 0;
	}

view raw boj-1509.cpp hosted with ❤ by GitHub