백준 1695번 팰린드롬 만들기

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

앞에서 뒤로 보나, 뒤에서 앞으로 보나 똑같은 숫자를 팰린드롬이라고 합니다.

따라서, 알고리즘은 아래와 같습니다.

1. arr[begin]==arr[end]라면 begin 인덱스는 하나 증가, end 인덱스는 하나 감소를 시킵니다.

2. arr[begin]!=arr[end]라면 조건 충족을 위해 숫자가 하나 추가되어야 하므로 begin 인덱스만 하나 증가시키거나 end 인덱스만 하나 감소시킵니다. 이 중, 더 작은 결과를 반환합니다.

#include <iostream>

#include <algorithm>

#include <cstring> //memset

using namespace std;

 

const int MAX = 5000;

 

int N;

int arr[MAX];

int cache[MAX][MAX];

 

int palindrome(int begin, int end)

{

        //기저 사례

        if (begin > end)

                 return 0;

 

        int &result = cache[begin][end];

        if (result != -1)

                 return result;

 

        if (arr[begin] == arr[end]) //조건 충족한다면

                 result = palindrome(begin + 1, end - 1);

        else //조건을 충족하지 않는다면

                 result = min(1 + palindrome(begin + 1, end), 1 + palindrome(begin, end - 1));

 

        return result;

}

 

 

int main(void)

{

        cin >> N;

 

        for (int i = 0; i < N; i++)

                 cin >> arr[i];

 

        memset(cache, -1, sizeof(cache));

 

        cout << palindrome(0, N - 1) << endl;

        return 0;

}

 

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~