BOJ(백준) 5502번 팰린드롬

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

5502번: 팰린드롬

서로 다른 방식의 두 가지 dp로 문제를 풀어보았다. 실행 시간은 1번 방법이 2번 방법보다 두 배 정도 더 빨랐다.

 

1. LCS를 활용한 방법

 

당연한 이야기지만 기존 문자열에 문자를 추가해 팰린드롬을 만든다면 추가할 문자는 기존에 존재하는 문자 중 하나에 대응하는(팰린드롬 상에서) 문자일 것이다.

 

그런데 여기서 문자를 추가하는 것은 추가할 문자에 대응하는 문자를 삭제하는 것과 동일하다.

 

따라서 최소 횟수를 구하는 방법은 다음과 같다.

 

원본 문자열과 그것을 뒤집은 문자열의 LCS(최장 공통 부분 문자열)을 구한다. 이후 그 외의 문자를 전부 지워버리면 되므로 (원본 문자열의 길이 - LCS의 길이)가 정답이 된다.

 

2. LCS를 활용하지 않는 방법

 

LCS구하는 방법을 몰라도 문제를 풀 수 있다.

 

우선 2차원 dp배열을 선언한다. (문자열 s에서, dp[i][k]=i번째 인덱스부터 k번째 인덱스를 팰린드롬을 만들기 위한 최소의 문자 추가 횟수)

 

dp[i][i]는 당연히 0이고 dp[i][i+1]은 s[i]==s[i+1]이라면 0 아니면 1로 초기화 해준다.

 

이제 길이가 3인 것부터 차례대로 1씩 길이를 늘리며 반복문을 돌 건데 점화식은 다음과 같다.

 

dp[i][k]=min(dp[i+1][k]+1, dp[i][k-1], s[i]==s[k] ? dp[i+1][k-1]:INF)

 

dp[i+1][k]+1는 s[i+1]~s[k]로 만든 팰린드롬의 오른쪽 끝에 s[i]와 같은 문자를 추가하는 것(=s[i]를 삭제하는 것)이고,

dp[i][k-1]+1는s[i]~s[k-1]로 만든 팰린드롬의 왼쪽 끝에 s[k]와 같은 문자를 추가하는 것(=s[k]를 삭제하는 것)이다.

마지막으로 s[i]==s[k] ? dp[i+1][k-1]:INF는 s[i]와 s[k]가 같다면  dp[i+1][k-1]의 문자열에 따로 바꾸지 않아도 되므로 그 값을 가져오는 것이다.

 

1번 방법 AC code

#include <bits/stdc++.h>
using namespace std;
int len,dp[5001][5001];
string s1,s2;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>len>>s1;
	s2=s1;
	reverse(s2.begin(),s2.end());
	for(int i=1;i<=len;i++) for(int k=1;k<=len;k++) {
		if(s1[i-1]==s2[k-1]) dp[i][k]=dp[i-1][k-1]+1;
		else dp[i][k]=max(dp[i-1][k],dp[i][k-1]);
	}
	cout<<len-dp[len][len];
}

 

2번 방법 AC code

#include <bits/stdc++.h>
using namespace std;
int len,dp[5001][5001];
string s;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>len>>s;
	for(int j=0;j<len-1;j++) dp[j][j+1]=s[j]!=s[j+1];
	for(int j=3;j<=len;j++) for(int l=0;l<=len-j;l++) dp[l][l+j-1]=min({dp[l][l+j-2]+1,dp[l+1][l+j-1]+1,s[l]==s[l+j-1]?dp[l+1][l+j-2]:INT_MAX});
	cout<<dp[0][len-1];
}

 

LCS를 안다면 1번 방법이 훨씬 더 간결하고 실행 시간이 빠르다는 점에서 더 좋은 것 같다.

 

설명에 이해가 안되는 부분이나 궁금하신 점이 있으면 언제든지 댓글로 물어봐주세요.

감사합니다.