[BAE/<JOON> 문제풀이] 1695. 펠린드롬 만들기

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

1695번: 팰린드롬 만들기

---

서론

어제까지 골4였는데 오늘보니까 골3 되어있음. 신기하다.

---

아이디어

사실 웰논 알고리즘만 알면 아이디어는 떠올리기 매우 쉽다.

LCS ( Longest Common String ) 라고 정말 옛날에 배운 알고리즘이다. 말 그대로 두 문자열에서 가장 긴 공통 문자열을 찾아내는 알고리즘이다. 팰린드롬이 되기 위해 필요한 추가 문자 갯수는 당연히 원본 배열 a와 인덱스를 뒤집은 배열 a'의 LCS 길이와 원본 배열 a 길이의 차가 될 것이다.

LCS 를 한번도 안해봤으면 직관만으로 떠올리긴 좀 힘들지 않나 싶다. 

---

풀이

이 문제에 대한 풀이라기보다 LCS 설명이 될 것 같다.

DP[i][j] = i 번째 a 배열과 j번째 b 배열까지의 가장 긴 LCS 길이

점화식 :

• i, j 번째 문자가 일치하는 경우
  이전에 일치했던 최대 길이 + 1을 해야 한다. 그런데 i, j 번째 문자는 현재 일치에 사용되었으므로 각각 -1을 해야한다.
  따라서 점화식은 DP[i][j] = DP[i - 1][j - 1] + 1
• i, j 번째 문자가 일치하지 않은 경우
  그냥 이전 결과 중 큰 거 고르면 된다. 이전 결과 2개 = i - 1 or j - 1
  따라서 점화식은 DP[i][j] = max(DP[i - 1][j], DP[i][j - 1])

시간 복잡도는 a, b 배열 길이의 곱이다. O(len(a) * len(b))

이 문제는 인덱스 역전만 했으니까 O(N^2)가 된다.

---

코드

인덱스 역전 배열을 별도로 만들지 말고 계산만 하면 코드가 깔끔하게 떨어진다.

#include <iostream>
#include <vector>
#include <string>
using namespace std;
int main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int n; cin >> n; vector<int> arr(n + 1); vector<vector<int>> dp(n + 1, vector<int>(n + 1));
	for (int i = 1; i <= n; i++) {
		cin >> arr[i];
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (arr[i] == arr[n - j + 1]) {
				dp[i][j] = dp[i - 1][j - 1] + 1;
			}
			else {
				dp[i][j] = dp[i][j - 1] > dp[i - 1][j] ? dp[i][j - 1] : dp[i - 1][j];
			}
		}
	}	
	cout << n - dp[n][n];
	return 0;
}