코드 복사/붙여넣기 하는 당신이 아름답습니다.

1509 : 팰린드롬 분할

풀이

나중에 써야징

코드

#include <stdio.h>
#include <string.h>

const int n_ = 2500 + 5;

int len, dp[n_][n_], res[n_];
char data[n_];

int main() {
	scanf("%s", data);
	len = strlen(data);

	for (int i = 1; i <= len; i++) dp[i][i] = 1;
	
	for (int i = 1; i <= len - 1; i++)
		if (data[i - 1] == data[i])
			dp[i][i + 1] = 1;

	for (int i = 2; i <= len - 1; i++)
		for (int j = 1; i + j <= len; j++)
			if (data[j - 1] == data[i + j - 1] && dp[j + 1][i + j - 1] == 1)
				dp[j][i + j] = 1;

	for (int i = 1; i <= len; i++) {
		if (res[i] == 0 || (res[i] > res[i - 1] + 1 && res[i] != 0))
			res[i] = res[i - 1] + 1;
		for (int j = i + 1; j <= len; j++)
			if (dp[i][j] && (res[j] == 0 || (res[j] > res[i - 1] + 1 && res[j] != 0)))
				res[j] = res[i - 1] + 1;
	}

	printf("%d", res[len]);

	return 0;
}

아무말

백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이

wookje.kwon's profile image

wookje.kwon

2017-03-13 09:09

Read more posts by this author