[ 백준 1509 ] 팰린드롬 분할 (C++)

백준의 팰린드롬 분할(1509) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

주어진 문자열의 최소의 팰린드롬 문자열로 분할 했을 때, 분할된 최소횟수를 구해야 하는 문제이다.

단계를 설정해서 순차적으로 문제에 접근해보자.

본인은 가장먼저 주어진 문자열을 팰린드롬 문자열로 판단하는 과정부터 진행해 주었다.

#1. 팰린드롬 문자열

지금부터 수식을 한 가지 사용할 것이다.

P[A][B] = true / false 라는 수식을 사용할 것인데, 이 수식의 의미는 다음과 같다.

P[A][B] = true : 주어진 문자열에서, A번문자부터 B번문자까지는 팰린드롬 문자열이 맞습니다.

P[A][B] = false : 주어진 문자열에서, A번문자부터 B번문자까지는 팰린드롬 문자열이 아닙니다.

그럼 문자열 "ABABA" 를 가지고 위의 수식 P[][]를 한번 채워보도록 하자.

(편의상, 가장 첫 번째 문자를 1번 문자, 가장 마지막 문자를 5번 문자 라고 표현하겠습니다.)

채우기 전에, 팰린드롬 문자열이 되기 위한 조건을 한번 생각해보자.

일단, 1차적으로는 "주어진 문자열에서 가장 첫 번째 문자와 가장 마지막 문자가 같아야 한다." 라는 것이다.

과연, 가장 첫 번째 문자와 가장 마지막 문자가 다를 때, 팰린드롬 문자열이 될 수 있는 문자열이 있을까 ??

절대 그럴 수가 없다. 즉, 첫 번째 조건으로는 "현재 문자열의 첫 번째 문자와 마지막 문자가 동일해야 한다." 라는 것이다.

2차적인 조건은, "1차적인 조건을 만족했을 때, 그 나머지 문자열들이 팰린드롬 문자열이어야 한다" 는 것이다.

예를 한번 들어보자.

"ABA" 라는 문자열을 한번 보자. 1차적인 조건을 확인했을 때, 가장 첫 문자인 'A'와 가장 마지막 문자인 'A'는 서로 동일하다. 즉, 1차적인 조건을 만족하는 경우이다. 2차적인 조건으로 그 나머지 문자열들을 보면, 그 사이에 있는 'B'라는 문자가 있다.

'B'라는 문자열은 밑에서 이야기를 하겠지만, 길이가 1인 문자열로써 ,그 자체만으로 팰린드롬 문자열이 된다.

즉, 1차적인 조건으로 "가장 첫 문자와 가장 마지막 문자가 동일" 하고, 2차적인 조건으로 "그 나머지 문자가 팰린드롬 문자열" 이므로,  "ABA"는 팰린드롬 문자열이 된다.

그럼, "ABCA" 라는 문자열을 한번 보자. 1차적인 조건은 만족한다. 그런데, 그 나머지 문자열인 "BC"를 확인했을 때 ,이 문자열은 팰린드롬 문자열이 아니다. 따라서, 이 문자열은 팰린드롬 문자열이 아니다.

이 2가지 조건을 생각하면서, "ABABA"에 대한 P[][] 값을 채워보자.

#1 - 1) 길이가 1인 문자열

길이가 1인 문자열은 그 자체만으로 팰린드롬 문자열이 된다.

예를 들어서 "A"라는 문자열은 이 자체만으로 팰린드롬 문자열이라는 것이다.

위에서 이야기한 2가지 조건에 대입을 해서 생각을 해봐도 무관하다.

1차적으로 가장 첫 문자와 가장 마지막 문자가 동일할 수 밖에 없고(길이가 1인 문자열이므로), 2차적으로 나머지 문자가 존재하지 않기 떄문에 무조건 팰린드롬 문자열이 된다.

즉, P[1][1] = P[2][2] = P[3][3] = P[4][4] = P[5][5] = true 라는 값을 설정할 수 있다.

#1 - 2) 길이가 2인 문자열

길이가 2인 문자열은 서로 같은 문자일 경우에만 팰린드롬 문자열이 된다.

예를 들어서 "AA"라는 문자열은, 앞에서부터 읽어도 "AA", 뒤에서부터 읽어도 "AA"로 동일하기 때문에 팰린드롬 문자열이 된다.

하지만, "AB"와 같이 서로 다른 2개의 문자로 이루어진 문자열은 팰린드롬 문자열이 아니다.

즉, "ABABA"에서 길이가 2인 팰린드롬 문자열은 존재하지 않는다.

#1 - 3) 길이가 3이상인 문자열

길이가 3이상인 문자열은 어떻게 구해야 할까 ??

지금부터는 위에서 이야기한 팰린드롬 문자열이 될 수 있는 2가지 조건을 잘 생각해보면 된다.

길이가 3이상인 문자열들은 다음과 같이 3가지 파트로 나눌 수가 있다.

[ 첫 번째 문자 ][ 나머지 문자열 ][ 마지막 문자 ]

이렇게 3가지 파트로 나눌 수가 있다. 길이가 1, 2인 문자열에 대해서는 위와 같이 나눌 수가 없었지만, 길이가 3이상인 문자열들은 위와 같이 나눌 수가 있다. 위와 같이 나누게 되면 우리가 이야기한 조건을 조금 더 쉽게 확인할 수 있다.

[ 첫 번째 문자]와 [ 마지막 문자 ] 가 동일해야 하고, [ 그 나머지 문자열 ] 이 팰린드롬 문자열이면 되는 것이다.

그럼, 첫 번째 문자의 Index번호를 'Start'라고 가정하고, 마지막 문자의 Index번호를 'End' 라고 가정해보자.

그럼, 그 나머지 문자열들의 Index번호는 어떻게 될까 ? 바로 Start + 1 ~ End - 1 이 될 것이다.

즉 ! 길이가 3 이상인 문자열들에 대해서는 다음과 같이 판단할 수 있다.

(주어진 문자열을 String 이라고 표현하겠습니다.)

String[Start] == String[End] && P[Start + 1][End - 1] == true

위의 조건을 만족한다면, P[Start][End] = true 라는 값을 설정할 수 있다.

따라서, 위와 같은 방식으로 길이가 1인 문자열부터 길이가 5인 문자열에 대한 모든 문자열에 대해서 팰린드롬인지 아닌지에 대해서 미리 판단해 줄 수가 있다.

#2. 분할 횟수 구하기

지금부터는 또 하나의 수식을 사용할 것이다.

F[A] = B 라는 수식을 사용할 것인데, "A번 문자까지 팰린드롬 문자열로 분할 할 수 있는 최소 횟수는 B번입니다."를 의미한다.

우리가 이 수식을 제대로 채웠다면 우리가 찾고자 하는 정답은 F[5] 에 저장되어 있을 것이다.

(현재 우리는 "ABABA"라는 문자열을 가지고 진행하고 있으므로 ! 실제 코드에서 정답은 F[문자열의 길이] 에 저장되어 있다.)

그럼 지금부터 "ABABA"라는 문자열을 가지고 진행해보자.

1) 1번 문자까지 분할할 수 있는 최소 횟수

1번 문자까지라고 하면 "A" 하나밖에 존재하질 않는다. 즉, 1번 문자까지 팰린드롬 문자열로 분할할 수 있는 최소 횟수는 1회가 된다. F[1] = 1

2) 2번 문자까지 분할할 수 있는 최소 횟수

2번 문자까지라고 하면 "AB"를 의미한다. 이 경우, "AB" 문자는 팰린드롬 문자열이 아니기 때문에 분할을 할 수가 없다.

따라서, 'A'와 'B'를 서로 나눠 주어야 한다. 이렇게 나누게 되면 문자열을 2개로 나눔으로써 팰린드롬 문자열로 만들 수가 있다.

F[2] = 2

3) 3번 문자까지 분할할 수 있는 최소 횟수

3번 문자까지의 문자열은 "ABA" 이다. 먼저, 이 문자열을 나눌 수 있는 모든 형태로 나눠보자.

1. "A" + "B" + "A"

2. "AB" + "A"

3. "A" + "BA"

4. "ABA"

위와 같이 4가지로 문자열로 나눠볼 수가 있다.

먼저 1번 Case를 한번 보자. "A" + "B" + "A" 로 나눈 형태인데, 모든 문자열들이 팰린드롬 문자열이 맞고, 이렇게 나누게 되면 총 3개의 문자열로 분할하게 된다.

2번, 3번 Case를 한번 보자. 이 경우에는 "올바르게 나누지 않은 경우" 이다. 왜냐하면 "AB" 와 "BA" 가 팰린드롬 문자열이 아니기 떄문이다. 따라서, 이 경우에는 올바르게 나누지 않은 경우이므로 비교를 할 필요가 없다.

4번 Case는 "ABA" 문자열 하나의 형태로 나눈 것인데, 이 경우에는 모든 문자열이 팰린드롬 문자열이 맞고, 이렇게 나누게 되면 총 1개의 문자열로 분할하게 된다.

따라서, 3번 문자까지 분할할 수 있는 최소 횟수는 "1회"가 된다.

F[3] = 1

그럼 여기서 보다 일반적인 이야기를 한번 해보자.

현재 End번 문자까지 분할할 수 있는 최소 횟수를 구하고자 한다.

그럼, 어떤 경우들을 비교를 해야할까 ?? 바로 P[1][End], P[2][End], ... P[End][End] 를 비교해 주면 된다.

그 중에서도 ! 팰린드롬 문자열인 경우, 즉, P[?][End] == true 일 경우에만 비교를 해주면 된다.

예를 들어서 P[A][End] = true 라고 가정해보자. 그럼 이 말은 즉, A번 문자부터 End번 문자까지로 이루어진 문자열은 팰린드롬 문자열이라는 것을 의미하고, A ~ End까지 하나의 문자열로 분할이 가능하다는 것을 의미한다.

이 떄, F[End]의 값은, F[A - 1] + 1 이 된다. 왜?? F[A - 1]이라는 값에 대해서 생각을 해보자.

현재 내가 찾은 문자열은 A ~ End번 문자로 이루어진 문자열인데, F[A - 1]이라는 것은, 이 전에 나왔던 문자(1 ~ A - 1번 문자) 까지의 팰린드롬 문자열로 분할할 수 있는 최소 횟수를 의미한다.

즉, F[A - 1]번 문자까지 분할할 수 있는 최소 횟수로 분할한 후에, A ~ End번 문자열을 하나의 팰린드롬 문자열로 분할을 할 것이기 때문에, 결국 1 ~ End번 까지의 최소 분할 횟수는 F[A - 1] + 1 이 된다는 것이다.

즉 ! F[End] = F[A - 1] + 1 이 된다는 것이다.

물론, 항상 이런것은 아니다. 왜 ?? 우리가 구해야 하는 것은 "최소 분할 횟수" 이기 때문에, A ~ End번 문자열이 팰린드롬 문자열로 분할이 가능하다고 하더라도, 기존에 구해놨던 최소횟수 중 더 작은 값이 있다면 갱신이 일어나면 안된다.

즉 ! F[End] = Min(F[End], F[A - 1] + 1) 이 되는 것이다.

[ 소스코드 ]

#include <iostream>
#include <cstring>
 
#define endl "\n"
#define MAX 2510
using namespace std;
 
int N;
int DP[MAX];
char String[MAX];
bool Palindrome[MAX][MAX];
 
int Min(int A, int B) { return A < B ? A : B; }
 
void Input()
{
    cin >> String + 1;
}
 
void Make_Palindrome()
{
    for (int i = 1; i <= N; i++) Palindrome[i][i] = true;
    for (int i = 1; i < N; i++)
    {
        if (String[i] == String[i + 1]) Palindrome[i][i + 1] = true;
    }
    for (int Len = 3; Len <= N; Len++)
    {
        for (int Start = 1; Start + Len - 1 <= N; Start++)
        {
            int End = Start + Len - 1;
            if (String[Start] == String[End] && Palindrome[Start + 1][End - 1] == true) Palindrome[Start][End] = true;
        }
    }
}
 
void Solution()
{
    for (N = 1; String[N] != NULL; N++); N--;
    
    Make_Palindrome();
    for (int End = 1; End <= N; End++)
    {
        DP[End] = 2e9;
        for (int Start = 1; Start <= End; Start++)
        {
            if (Palindrome[Start][End] == true)
            {
                DP[End] = Min(DP[End], DP[Start - 1] + 1);
            }
        }
    }
    cout << DP[N] << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}