이것 저것 &

문제링크:www.acmicpc.net/problem/5502

해당 문제는 lcs와 연관이 있다.

LCS의 갯수를 통해서 팰린드롬을 위한 갯수 도출할수 있기 때문입니다.

논리자체는 굉장히 간단하다.

• 1. 입력받은 문자열과 문자열을 뒤집은 것과의 lcs 구하기
• 2. N - LCS 이 정답

우선 lcs는 아래 링크를 통해서 이해하자

gusdnr69.tistory.com/192

아래는 정답코드이다.

팰린드롬이 LCS와 연관이 있다는 것을 이해하는 것이 어려운 문제이고, 

구현 난이도는 매우 낮은 문제이다.

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

int n = 0;
string arr;
string arr_re;
int dp[5001][5001] = { 0, };

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);

	cin >> n;
	cin >> arr;
	arr_re = arr;
	reverse(arr_re.begin(), arr_re.end());
	for (int i = 0; i < n; i++) {
		if (arr_re[0] == arr[i]) dp[0][i] = 1;
		else if(dp[0][i - 1] == 1)dp[0][i] = 1;

		if (arr_re[i] == arr[0]) dp[i][0] = 1;
		else if (dp[i - 1][0] == 1)dp[i][0] = 1;
	}

	for (int i = 1; i < n; i++) {
		for (int j = 1; j < n; j++) {
			if (arr_re[i] == arr[j]) dp[i][j] = dp[i - 1][j - 1] + 1;
			else {
				dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
			}
		}
	}
	/*
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cout << dp[i][j] << ' ';
		}
		cout << endl;
	}*/

	cout << n - dp[n - 1][n - 1] << endl;


	return 0;
}