백준/1509번/팰린드롬 분할/골드1

Problem Link: https://www.acmicpc.net/problem/1509

문제 설명

Site: Baekjoon
Number: 1509
Category: Dynamic Programming
Rank: Gold 1

대문자 알파벳으로 이루어진 문자열이 주어졌을 때, 팰린드롬으로 분할한다면 나오는 팰린드롬의 갯수의 최소값을 구하는 문제입니다.

문제 풀이

첫 문제 풀이는 각 위치 별 모든 팰린드롬을 검사하여 진행하였습니다. 정답은 도출되었지만, 너무 많은 시간이 소요되어 팰린드롬을 저장하여 판별하는 방식을 두 번째 풀이에 사용하였습니다.

첫 번째 풀이

주어진 문자열을 모든 위치를 돌며 해당 위치까지 다시 for문을 통해 팰린드롬 존재여부를 판별하고 최소값을 갱신하는 방식입니다.

Palindrome 판별에 대한 중복이 너무 많아 정답은 나왔지만 1744ms라는 속도로 매우 느리게 검사되었습니다.

#include <iostream>
#include <algorithm>

using namespace std;

int dp[2501];

bool CheckPalindrome(string str)
{
    string tmp = str;
    reverse(tmp.begin(), tmp.end());

    if (str == tmp)
        return true;

    return false;
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    string str;
    cin >> str;

    dp[1] = 1;
    dp[2] = (str[0] == str[1]) ? 1 : 2;

    string s = str.substr(0, 2);

    for(int i = 3; i < str.length()+1; i++)
    {
        s.push_back(str[i-1]);

        dp[i] = dp[i - 1] + 1;

        for(int j = 0; j < i; j++)
        {
            string tmp = s.substr(j, i - j);

            if (CheckPalindrome(tmp))
                dp[i] = min(dp[i], dp[j] + 1);
            else
                dp[i] = min(dp[i], dp[i - 1] + 1);
        }
    }

    cout << dp[str.length()];

    return 0;
}

두 번째 풀이

Palindrome 중복 판별을 줄이기 위해 Palindrome 판별에 대한 값을 미리 저장하는 방식입니다.

check 배열의 의미는 check[i][j]에서 i부터 j까지 Palindrome인지에 대한 여부를 bool 값으로 저장한 것입니다.

배열을 주어진 문자열 크기 만큼 한번 돌며 check[i][i]는 true로, check[i][i+1]은 이어진 두 단어가 동일할 시 true 아니라면 false로 설정합니다.

다음은 길이가 3 이상부터 전체 문자열 팰린드롬의 판별하여 저장합니다.

#include <iostream>

using namespace std;

int dp[2502];
bool check[2502][2502];

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    string str;
    cin >> str;

    int s = str.size();

    str = " " + str;

    for (int i = 0; i <= s; i++)
    {
        check[i][i] = true;
        check[i][i + 1] = str[i] == str[i + 1];
    }

    for(int i = s - 2; i >= 0; i--)
    {
	    for(int j = i + 2; j <= s; j++)
	    {
            check[i][j] = check[i + 1][j - 1] & (str[i] == str[j]);
	    }
    }

    dp[1] = 1;
    dp[2] = check[1][2] ? 1 : 2;

    for(int i = 3; i <= s; i++)
    {
        dp[i] = dp[i - 1] + 1;
	    for(int j = 1; j < i; j++)
	    {
            if (check[j][i])
            {
                dp[i] = min(dp[i], dp[j-1] + 1);
            }
	    }
    }

    cout << dp[s];

    return 0;
}