[BOJ][C/C++] 1509번 : 팰린드롬 분할

AJM·2024년 4월 20일

백준

백준 문제 풀이

목록 보기

16/19

🔗링크

1. 문제 풀이

이 문제는 두가지의 DP 알고리즘을 활용하여 풀이하였다.

1. 펠린드롬 판단

N의 크기가 2,500이기에 일반적인 O(n^2) 알고리즘을 사용하기엔 비용이 너무 크다.

그렇기에 다른 방식으로 주어진 문자열을 판단한다.

우선 가장 작은 펠린드롬은 길이가 1인 문자열이다.

$Str[i] == Str[j], (i = j)$

여기서 길이가 4인 팰린드롬 문자열은 다음과 같다

$Str[i] = Str[j]\\ \\ and \\ \\ Str[i +1] = Str[j - 1],(i+1=j-1)$

여기서 알 수 있는 사실은

i에서 시작하고 j에서 끝나는 문자열이 펠린드롬이기 위해서는
i + 1에서 시작하고 j - 1에서 끝나는 문자열이 펠린드롬이어야 한다.

즉 Palin[i][j]가 참이기 위해선 Str[i] == Str[j] 이면서 Palin[i+1][j-1] 또한 참이어야 한다.

이를 활용해 DP로 펠린드롬 판단이 가능해진다.

int table[2501][2501];

int is_palindrome(int i,int j) {
	if (str[i] == str[j]) { //Str[i] != Str[j]이면 펠린드롬일 수 없다
	
		if (j - i <= 2) return table[i][j] = 1; // 문자열의 길이가 1,2,3일때 예외 처리
		
		else return table[i][j] = table[i + 1][j - 1]; //i ~ j 사이가 펠린드롬이면 참
		
	}
	else return 0;
}

2. 분할 개수 구하기

앞선 알고리즘으로 펠린드롬을 빠르게 판단 가능해졌다.

분할의 최소개수를 구하는것 역시 DP로 해결하면 된다.
DP[i] = 0~i까지의 최소 분할 개수
만약 j ~ i의 범위가 펠린드롬이라면
DP[j - 1] + 1와 DP[i] 중 작은값을 취한다.

위의 식으로 최소 분할 개수를 구하면 된다.

int f() {
	N = strlen(str);
	for (int i = 1; i <= N; i++) {
		dp[i] = 2501;
		for (int j = 1; j <= i; j++) {
			if (is_palindrome(j - 1, i - 1)) // dp[1]부터 시작하기 때문에 범위는 -1씩 해줌
				dp[i] = min(dp[i], dp[j - 1] + 1);
		}
	}
	return dp[N];
}

2. 코드

#include<stdio.h>
#include<string.h>
#define min(a,b)(a<b?a:b)

int dp[2501] = {0,1}, N;
int table[2501][2501];
char str[2501];

int is_palindrome(int i,int j) {
	if (str[i] == str[j]) {
		if (j - i <= 2) return table[i][j] = 1;
		else return table[i][j] = table[i + 1][j - 1];
	}
	else return 0;
}

int f() {
	N = strlen(str);
	for (int i = 1; i <= N; i++) {
		dp[i] = 2501;
		for (int j = 1; j <= i; j++) {
			if (is_palindrome(j - 1, i - 1))
				dp[i] = min(dp[i], dp[j - 1] + 1);
		}
	}
	return dp[N];
}

int main() {
	scanf("%s",str);
	printf("%d", f());
	return 0;
}