[백준] 1695-팰린드롬 만들기(C++)

문제링크:https://www.acmicpc.net/problem/1695

1695번: 팰린드롬 만들기

 

팰린드롬은 앞으로 보나 뒤로 보나 대칭인 값입니다. 

 

해당 팰린드롬 만들기를 구현하기 위해서는 dp 관점으로 접근해야합니다. 

저는 직관적인 점화식을 유추하지 못했습니다.

 

분명 재귀를 쓰지않고 구현하는 방법이 있을텐데, 못찾고 인터넷의 힘을 빌렸습니다.

 

우선 정답코드입니다.

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
int n = 0, result = 0;
int arr[5001] = { 0 };
int dp[5001][5001] = { 0 };

int solved(int started, int ended) {
	if (started == ended || started > ended) return 0;

	int& ret = dp[started][ended];
	if (ret != -1) return ret; //방문햇엇고, 이미 결과가 있으면 그걸 사용한다는 것 
	ret = 0;

	if (arr[started] == arr[ended])
		ret += solved(started + 1, ended - 1);

	else {
		ret += min(solved(started, ended - 1) + 1, solved(started + 1, ended) + 1);
	}

	return ret;
}

int main() {
	cin >> n;

	for (int i = 0; i < n; i++)
		cin >> arr[i];
	memset(dp, -1, sizeof(dp));

	result = solved(0, n - 1);

	cout << result << endl;

	return 0;
}

 

up-down 방식으로 구현하였습니다 

 

5

1 2 3 4 2 와 같은 예시에서

 

1 2 3 4 2 에서  양끝 1 과 2를 비교합니다. 두 값이  같지않을 때 두가지 방법이 존재합니다.

• 1을 가르키는 화살표를 오른쪽 방향으로 옮기고 2뒤에 1를 추가한다.  ->  1 2 3 4 2 (1)
• 2를 가르키는 화살표를 왼쪽 방향으로 옮기고  1앞에 2를 추가한다.    ->  (2) 1 2 3 4 2

만약 두값이 같다면 화살표를 둘다 안쪽으로 옮기고 값을 유추합니다. -> 1 2 3 4 2 (1)   -> 1 2 3 4 2 (1)  

 

 1 2 3 4 2 (1) 이와같은 상황에서는 두가지 방법을 적용해보고 그중 작은 값을 반환합니다. (1을 반환하게 됩니다.)

3 4 3 or 4 3 4  구조가 되면 내부적으로 1을 반환합니다. 

 

결과값은 1 2 3 4 (3) 2 (1) 으로 2가 됩니다. 

 

 

재귀함수를 통해 구현하며 ret 값이 -1이 되었다면 이미 한번 탐색한 곳이기 때문에 바로 해당값을 반환합니다.(메모이 제이션)