boj 1509 - 팰린드롬 분할

개요

2개의 DP가 엮여있는 문제입니다. 

1. 부분 문자열 str[a:b]가 팰린드롬인지 판단하고 저장하는 배열을 생성하는 과정

2. 부분 문자열 str[0:c]의 팰린드롬 분할 최소 값을 파악하고 저장하는 배열을 생성하는 과정

 

예제

백준 예제를 예시로 들겠습니다.

ABACABA

 

 

1. 부분 문자열 str[a:b]가 팰린드롬인지 판단하는 과정

해당 과정은 2차원 배열을 통해서 이뤄집니다. dp[i][j]가 갖는 값은 str[i:j]가 팰린드롬이라면 true를, 그렇지 않으면 false를 갖는 boolean 배열입니다.

1) 가장 먼저, dp[i][i]는 모두 true입니다. 1글자의 문자열은 모두 팰린드롬이라고 볼 수 있기 때문이죠.

• dp[0][0]의 값은 'A'가 팰린드롬인가? 를 의미하며 true입니다.
• dp[3][3]의 값은 'C'가 팰린드롬인가? 를 의미하며 true입니다.

2) $i \neq j$인 dp[i][j]를 고민해봅시다. 이 때 다음과 같이 두 가지로 다시 나눠볼 수 있습니다.

2-1) j-i가 1인 경우 (e.g., dp[0][1], dp[4][5])

2-2) 그렇지 않은 경우 (e.g., dp[2][4])

 

2-1) j-i가 1인 경우 (e.g., dp[0][1], dp[4][5])

이는 두 글자 문자열을 의미합니다. 따라서 $str[i] == str[j]$인 경우에만 true가 보관됩니다. 이 예제에서는 아쉽게도 존재하지 않네요.

 

 

2-2) $j-1 \neq i$ 인 경우 (e.g., dp[2][4])

 이 때는 지금까지 구해 놓은 값을 바탕으로 쉽게 확인할 수 있습니다. str[i:j]가 팰린드롬일 조건은

(1) $str[i] == str[j]$ 이면서

(2) $dp[i+1][j-1] == True$인 경우

str[i:j]가 팰린드롬이 되는 것이죠. (2) 이미 팰린드롬인 문자열 앞 뒤에 (1) 같은 문자열이 붙으면 팰린드롬이겠죠?

 

 dp[0][2]의 값은 ABA가 팰린드롬인지? 를 의미합니다. dp[0+1][2-1] = dp[1][1] = T이고, str[0] == str[2] == 'A' 이므로 dp[0][2]는 T가 됩니다.

 

이런 식으로 모든 배열을 채워나가면 됩니다.

 

 (배열을 채워 나가는 순서는 대각선 순으로, 가로 순으로, 세로 순으로 중에 어느것도 상관 없습니다. 단지, 값을 참조할 dp[i+1][j-1]가 dp[i][j]보다 먼저 계산이 완료되기만 하면 됩니다.)

 

2. 부분 문자열 str[0:c]의 팰린드롬 분할 최소 값을 파악하는 과정

자, 이제 위에서 구한 테이블을 기준으로 부분 문자열 str[0:c]의 최소 팰린드롬 분할을 구해봅시다. 위의 배열과 구분하기 위해서 배열의 이름을 ans라고 하겠습니다.

 

1) 첫 글자는 하나의 팰린드롬으로 볼 수 있으므로 1이 됩니다.

 

 

2) ans[1]은 dp[_][1]을 순회하며 구합니다.

 dp[_][1]을 순회해보면, str[_:1] 중에서 팰린드롬을 만들 수 있는 경우는 자기 자신 dp[1][1]밖에 없습니다. 따라서 분할되어야 하며, ans[0]의 값에 +1을 해줍니다. {A, B}

 

3) ans[2]도 dp[_][2]를 순회하며 구합니다.

dp[_][2]를 순회하면 dp[0][2]와 dp[2][2]가 팰린드롬입니다. 따라서 분할 방법 개수가 2가지가 되네요.

• dp[0][2]: "ABA"자체가 하나의 팰린드롬으로 분할이 가능합니다. 따라서 이 때 ans[2]는 1이 됩니다.
• dp[2][2]: "A"가 팰린드롬임을 이용하겠다는 뜻입니다. 이 경우에는 str[0:1]의 최소 팰린드롬 분할 개수를 이용하여 ans[2]를 구해야 합니다. 즉, 3이 됩니다.

위 두 가지 케이스에서 최소 값을 보관합니다. 따라서 ans[2]는 3이 됩니다.

 

4) 같은 방식으로 모두 순회

 

5) 정답

ans[6]에 있는 값 1이 정답이 됩니다. 

코드

#include <stdio.h>
#include <string.h>

bool palindrome[2501][2501];
int ans[2501];
int main(){
    char str[2501];
    int len = 0;
    scanf("%s", str);
    len = strlen(str);

    for (int i = 0; i < len; i++) {
        palindrome[i][i] = true;
        ans[i] = 2501;
    }

    for (int j = 1; j < len; j++) {
        for (int i = 0; i < j; i++) {
            bool match = str[i] == str[j];
            if (!match) 
                continue;
            palindrome[i][j] = j - i == 1 ? true : palindrome[i+1][j-1];
        }
    }

    for (int j = 0; j < len; j++) {
        for (int i = 0; i <= j; i++) {
            if (!palindrome[i][j])
                continue;
            if (i == 0) {
                ans[j] = 1;
            } else if (ans[j] > ans[i-1] + 1) {
                ans[j] = ans[i-1] + 1;
            }
        }
    }

    printf("%d\n", ans[len-1]);
    return 0;
}