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

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

1695번: 팰린드롬 만들기

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int N;
int arr[5001];
int dp[5001][5001];

int func(int s, int e)
{
    if(s>=e) return 0; //탐색 종료
    if(dp[s][e]) return dp[s][e]; //중복방지
    if(arr[s]==arr[e]) dp[s][e] = func(s+1, e-1); 
    else dp[s][e] = min(func(s, e-1)+1, func(s+1, e)+1); //왼쪽과 오른쪽중 최솟값 택 1
    return dp[s][e];
}

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);
    
    cin >> N;
    for(int i=0; i<N; i++) cin >> arr[i];

    cout << func(0, N-1);

    return 0;
}

 

상당히 유명한 팰린드롬과 관련된 dp 문제이다.

맨좌측과 맨오른쪽이 같은지 아닌지를 비교해야하기 때문에 시작점과 끝점을 맨좌측값과 맨오른쪽값으로 잡는다.

 

각 위치의 값이 같다면 현재 팰린드롬을 만족하는 상태이다.

따라서 왼쪽값과 오른쪽값 모두 하나씩 이동시켜준다.

 

각 위치의 값이 다르다면 팰린드롬을 만족하지 않으므로 팰린드롬 상태를 만족시켜주기 위해 값을 하나 추가해주어야 하는 상태이다.

왼쪽에 값을 추가시켜줄지, 오른쪽에 값을 추가시켜줄지를 2개 모두 돌려서 작은 값인 쪽을 선택해준다.

왼쪽을 추가하였을 때는 오른쪽값을 이동시키고 오른쪽값을 추가하였을 때는 왼쪽 값을 이동시켜준다.

이렇게 시작점과 끝점이 계속 이동하다가 둘의 위치가 같아지면 값을 모두 탐색한 것이므로 종료시켜준다.

 

팰린드롬을 만들어주면서 + 1을 해주고, 이때 모두 더한 최솟값이 우리가 찾는 결과값이 된다.

 

<1 2 3 4 2>

1!=2
맨 오른쪽 1 추가, 왼쪽 값 이동
-> 2 3 4 2

2 2 동일 
-> 3 4

3!=4

오른쪽 추가 or 왼쪽 추가 (동일)
값 1개 추가 확정

3 or 4
값이 하나 남았으므로 종료

총 추가 값 2