[BAEKJOON] 1695 팰린드롬 만들기

#define _CRT_SECURE_NO_WARNINGS #include <iostream> #include <vector> #include <algorithm> using namespace std; vector<vector<int>>dp; vector<int>str; int makePaline(int start, int end) { if (start >= end) return 0; int&ret = dp[start][end]; if (ret != 0) return ret; if (str[start] == str[end]) return makePaline(start + 1, end - 1); return ret = min(makePaline(start + 1, end), makePaline(start, end - 1)) + 1; } int main() { int n; scanf("%d", &n); dp = vector<vector<int>>(n + 1, vector<int>(n + 1, 0)); str = vector<int>(n + 1); for (int j = 0; j < n; j++) scanf("%d", &str[j]); printf("%d", makePaline(0, n - 1)); return 0; }