[백준] 1695번: 팰린드롬 만들기 (c++)

 

문제

---

앞에서 뒤로 보나, 뒤에서 앞으로 보나 같은 수열을 팰린드롬 이라고 한다. 예를 들어 {1}, {1, 2, 1}, {1, 2, 2, 1}과 같은 수열은 팰린드롬 이지만, {1, 2, 3}, {1, 2, 3, 2} 등은 팰린드롬이 아니다.

한 수열이 주어졌을 때, 이 수열에 최소 개수의 수를 끼워 넣어 팰린드롬을 만들려고 한다. 최소 몇 개의 수를 끼워 넣으면 되는지를 알아내는 프로그램을 작성하시오.

 

1695번: 팰린드롬 만들기

 

문제조건

---

첫째 줄에 수열의 길이 N(1≤N≤5,000)이 주어진다. 다음 줄에는 N개의 수열을 이루는 수들이 주어진다. 각 수들은 int 범위이다.

 

풀이

---

top-down으로 풀어보았다. 팰린드롬이 되기 위해서는 가장 끝 두 수들의 값이 동일해야 한다. 앞쪽 수를 arr[s], 뒤쪽 수를 arr[e]라 하자.

1️⃣ 동일한 경우(arr[s]==arr[e]) ➡ arr[s+1], arr[e-1] 비교

(두 수가 다른 경우, 개수 1 증가)
2️⃣ arr[s] 앞에 arr[e] 값을 넣기 ➡ arr[s], arr[e-1] 비교
3️⃣ arr[e] 뒤에 arr[s] 값을 넣기 ➡ arr[s+1], arr[e] 비교

두 수가 다른 경우에는 2,3번을 시도해 본 후 더 작은 값을 고르면 된다. 이 과정에서 이미 찾은 값을 다시 구하는 경우가 생길 수 있으므로 memorization을 사용했다. 구간 값을 구했다면 dp[s][e]로 값을 저장하여 추후에 다시 s~e값이 필요할 때 사용하였다.

 

코드

---

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;
int n;
int arr[5001];
int dp[5001][5001];

int pal(int s, int e) {
	if (s >= e) return 0; // 종료조건

	if (dp[s][e] != -1) return dp[s][e];
    
	int cnt = 0;
	if (arr[s] == arr[e]) {
		cnt = pal(s + 1, e - 1);
	}

	else {
		// s앞에 arr[e] 값 추가, e뒤에 arr[s] 값 추가
		cnt = min(pal(s, e - 1) + 1, pal(s + 1, e) + 1);
	}

	return dp[s][e] = cnt;
}


int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			dp[i][j] = -1;
		}
	}

	cout << pal(0, n - 1);
}