백준 1509번 팰린드롬 분할

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

http://jaimemin.tistory.com/453에서 최소 분할 개수를 판별하는 함수만 추가하면 되는 문제였습니다.

최소 분할 개수를 판별하기 위해서는 0번째 인덱스를 비워놓아야 했기 때문에 문자열을 입력 받은 다음에 한칸씩 뒤로 밀어서 저장했습니다.

#include <iostream>

#include <string>

#include <algorithm>

#include <cstring> //memset

using namespace std;

 

const int MAX = 2500 + 1;

const int INF = 98754321;

 

string str;

char S[MAX];

int cache[MAX][MAX];

int minResult[MAX];

 

int palindrome(int start, int end)

{

        //기저 사례

        if (start >= end)

                 return 1;

       

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

        if (result != -1)

                 return result;

 

        if (S[start] != S[end])

                 return result = 0;

        return result = palindrome(start + 1, end - 1);

}

 

int getMinResult(void)

{

        minResult[0] = 0; //1번째 인덱스부터 문자열이 시작되므로

        for (int i = 1; i <= str.length(); i++)

        {

                 minResult[i] = INF;

                 for (int j = 1; j <= i; j++)

                         //팰린드롬이라면 하나 추가하고 갯수가 최소인지 판별

                         if (palindrome(j, i))

                                 minResult[i] = min(minResult[i], minResult[j - 1] + 1);

        }

        return minResult[str.length()];

}

 

int main(void)

{

        cin >> str;

 

        //index는 1부터 시작

        for (int i = 0; i < str.length(); i++)

                 S[i + 1] = str[i];

       

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

       

        cout << getMinResult() << endl;

 

        return 0;

}

개발환경:Visual Studio 2017

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