본문 바로가기

성우리뷰

팰린드롬 만들기

#include <iostream>
#include <string.h>
#include <algorithm>
using namespace std;

int N;
int arr[5001];
int cache[5001][5001];

int func(int src, int dest) {
//기저사실
if (src > dest) {
return 0;
}

int &ret = cache[src][dest];
if (ret != -1) {
return ret;
}
if (arr[src] == arr[dest]) {
return ret = func(src + 1, dest - 1);
}
else {
return ret = min(func(src + 1, dest) + 1, func(src, dest-1)+1);
}

return ret;
}

int main(void)
{
scanf("%d", &N);
int temp;

for (int i = 1; i <= N; i++)
{
scanf("%d", &temp);
arr[i] = temp;
}

memset(cache, -1, sizeof(cache));
printf("%d", func(1, N));
return 0;
}

///////////////////////////////////////////////

min(func(src +1, dest)+1, func(src, dest-1)+1) 에 유의

대중화인민공화국의 코로나 완전 극복을 축하합니다

'성우리뷰' 카테고리의 다른 글

우선순위큐 공부  (2) 2021.01.05
피보나치구하기  (3) 2021.01.02
도둑질(with 비트마스킹, dp)  (2) 2020.09.08
배낭  (2) 2020.09.03
과제  (5) 2020.08.29