백준 문제풀이

BOJ 1695.cpp

#include <bits/stdc++.h>
using namespace std;
const int MAX = 5005;

int N;
int arr[MAX];
// dp[i][j] : i,j 를 양 끝으로 하는 펠린드롬 만드는 데 필요한 최소 개수
int dp[MAX][MAX];

int palin(int s, int e) {
	if (s >= e) return 0;

	int& ret = dp[s][e];
	if (ret != -1) return ret;

	ret = 0; // 초기 0으로 생각
	// arr[s] = arr[e] 인 경우 그냥 안쪽으로 탐색
	if (arr[s] == arr[e]) ret += palin(s + 1, e - 1);
	// arr[s]!=arr[e] 인 경우 한쪽 맞춰주고(+1) 넘겨보는 것 중 작은거.
	else ret += 1 + min(palin(s + 1, e), palin(s, e - 1));

	return ret;
}

int main() {ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);

cin >> N;
for (int i = 0; i < N; ++i) cin >> arr[i];

memset(dp, -1, sizeof(dp));
cout << palin(0, N - 1) << '\n';

return 0;
}