백준 1695 팰린드롬 만들기

www.acmicpc.net/problem/1695

1695번: 팰린드롬 만들기

백준 1695 팰린드롬 만들기

팰린드롬이란 광고의 문구 앞뒤가 똑같은 전화번호와 똑같이 앞과 뒤가 같은 문자열을 뜻한다. 비슷한 문제로 이 문자열이 팰린드롬인지 판단하는 문제는 있었지만 이 문제의 경우 몇개의 숫자를 끼워 넣어야 팰린드롬이 되는지 맞추는 것이다.

 

우선 팰린드롬이 되는 규칙을 찾아야한다. 

 

1 2 3 4 2

 

1, 2, 3, 4, 2의 경우 2는 짝꿍이 되니 2 뒤로 1을 넣어 주어 팰린드롬의 규칙을 맞추어 갈 수 있다. 즉 앞뒤가 다르게 판단하는 경우 1일 증가시켜서 팰린드롬을 만들어줄 수 있다. 

 

팰린드롬을 확인시켜주기 위해서 검색을 진행해야하는데

 

 

S E의 인덱스가 가르키는 값이 같을 때 

 

S + 1, E - 1을 후재구

 

S, E의 인덱스가 가르키는 값이 다를 때는 

 

S+1 E, S E-1로 인덱스를 나누어서 재귀를 실행시켜 주면된다.

 

dp배열에 값이 정해졌는데 다시 재귀를 하면 시간초과가 발생할 수 있기 때문에 이미 방문한적이 있다면 그냥 반환해주자!

#include <cstdio>
#include <algorithm>
#include <string.h>

using namespace std;

int N;
int arr[5002], dp[5002][5002];
int maxValue = 0;

int palin(int S, int E){
	if(S >= E)
		return 0;

	if(dp[S][E] >= 0)
		return dp[S][E];

	if(arr[S] == arr[E]){
		dp[S][E] = palin(S+1, E-1);
		return dp[S][E];
	}else{
		dp[S][E] = min(palin(S+1, E), palin(S, E-1)) + 1;
		return dp[S][E];
	}
}

int main(){
	scanf("%d", &N);
	memset(dp, -1, sizeof(dp));
	for(int i = 0; i < N; i++)
		scanf("%d", &arr[i]);
	
	palin(0, N-1, 0);

	printf("%d", dp[0][N-1]);	
}