[BOJ] 5502 팰린드롬

문제 링크

 

www.acmicpc.net/problem/5502

 

모든 알고리즘 문제는 C++로 구현되어 있습니다.

 

주어진 문자열과 이를 뒤집은 문자열의 LCS를 구한 뒤, 전체 문자열 길이에서 이를 빼주면 답을 구할 수 있는 문제이다. 방법을 알면 구현 자체는 쉽지만, 방법을 떠올리기가 어려워 애를 먹었던 문제였다. 한번 경험해봤으니 다음에 비슷한 문제가 나오면 LCS로 접근을 해봐야겠다.

 

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int dp[5000][5000];
int main() {
	int i, j, n;
	string s, sRev;
	cin >> n >> sRev;
	s = sRev;
	reverse(sRev.begin(), sRev.end());
	for (i = 0; i < n; i++) {
		if (s[i] == sRev[0] || (i > 0 && dp[0][i - 1] == 1)) dp[0][i] = 1;
		if (sRev[i] == s[0] || (i > 0 && dp[i - 1][0] == 1)) dp[i][0] = 1;
	}

	int ret = 0;
	for (i = 1; i < n; i++) {
		for (j = 1; j < n; j++) {
			if (sRev[i] == s[j]) dp[i][j] = dp[i - 1][j - 1] + 1;
			dp[i][j] = max(dp[i][j], max(dp[i - 1][j], dp[i][j - 1]));
			ret = max(ret, dp[i][j]);
		}
	}
	cout << n - ret;
}