[BOJ/백준][Gold4] 1695 : 팰린드롬 만들기 (C++)

www.acmicpc.net/problem/1695

1695번: 팰린드롬 만들기

 

[난이도] Gold4

[유형] DP

 

[풀이]

top-down dp로 해결할 수 있다.

 

sol(l,r) : 왼쪽 index가 l, 오른쪽이 r일때 팰린드롬을 만들기 위해 추가해야되는 숫자의 개수.

 

점화식

case l==r : sol(l,r) = sol(l+1,r-1)

case l!=r : sol(l,r) = min(sol(l,r-1)+sol(l+1,r))

 

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n,a[5000],dp[5000][5000];

int sol(int l,int r){
    if(l>=r) return 0;
    int& ret = dp[l][r];
    if(ret !=-1) return ret;
    if(a[l]==a[r]) ret = sol(l+1,r-1);
    else ret = min(sol(l,r-1),sol(l+1,r))+1;
    return ret;
}
int main(){
    scanf("%d",&n);
    for(int i=0;i<n;i++) scanf("%d",&a[i]);
    memset(dp,-1,sizeof(dp));
    printf("%d",sol(0,n-1));
}

 

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold4/1695.cpp