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

문제

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

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

입력

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

출력

첫째 줄에 끼워 넣을 수들의 최소 개수를 출력한다.

---

수열의 중간에 원하는 수를 추가해서 얻을 수 있는 가장 짧은 팰린드롬을 구해야 한다.

예를들어 1 2 3 1이라면 중간에 2 또는 3을 추가해서 12321, 13231 이라는 팰린드롬 수열을 구할 수 있다.

 

dp를 이용해 해결할 수 있다.

dp[start][end] : start ~ end 지점에서 끼워 넣을 수의 최소 개수라고 하자.

이미 팰린드롬이라면 0일 것이다.

 

만약 start와 end인덱스에 해당하는 수가 같다면 dp[start][end] = dp[start+1][end-1]이 될 것이다.

다르다면, dp[start][end] = min(dp[start+1][end, dp[start][end-1]) + 1 이 될 것이다. 

 

이 점화식이 성립하도록 적절하게 구현해주자.

 

코드 원본 : https://github.com/chosh95/STUDY/blob/master/BaekJoon/2020/%ED%8C%B0%EB%A6%B0%EB%93%9C%EB%A1%AC%20%EB%A7%8C%EB%93%A4%EA%B8%B0%20(1695%EB%B2%88).cpp

chosh95/STUDY

 

C++ 코드

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

int N;
int p[5001];
int dp[5001][5001];

int dfs(int start, int end) {
	if (start >= end) return 0;

	if (dp[start][end] != 0) return dp[start][end];

	int cur = 987654321;
	if (p[start] == p[end])
		cur = min(cur, dfs(start + 1, end - 1));
	else {
		cur = min(dfs(start,end-1) + 1, dfs(start + 1, end) + 1);
	}
		
	return dp[start][end] = cur;
}

int main()
{
	cin >> N;
	for (int i = 0; i < N; i++)
		cin >> p[i];

	cout << dfs(0, N - 1);
}