[백준] 1509번: 팰린드롬 분할

1509번: 팰린드롬 분할

문제

세준이는 어떤 문자열을 팰린드롬으로 분할하려고 한다. 예를 들어, ABACABA를 팰린드롬으로 분할하면, {A, B, A, C, A, B, A}, {A, BACAB, A}, {ABA, C, ABA}, {ABACABA}등이 있다.

분할의 개수의 최솟값을 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 문자열이 주어진다. 이 문자열의 최대길이는 2,500이다.

출력

첫째 줄에 팰린드롬 분할의 개수의 최솟값을 출력한다.

예제 입력 1

BBCDDECAECBDABADDCEBACCCBDCAABDBADD

예제 출력 1

22

 

 

---

 

 

작심삼일, 딱 삼일 째입니다! 하루에 한 문제 풀기 Challenge? ㅎㅎ

[백준] 10942번: 팰린드롬?

시작은 이 문제와 굉장히 비슷하게 접근할 수 있습니다. pal 배열에 start index 부터 end index 까지가 팰린드롬인지 판별된 결과를 저장합니다. 그 다음엔 일반적인 다이나믹 프로그래밍 문제와 비슷하게 풀이를 해나갑니다.

pal 배열을 만드는 것에 대한 설명은 위의 문제를 참고해주세요!

 

다이나믹 프로그래밍 문제를 풀 때는, 위의 문제에서도 언급했었는데 0번 인덱스가 비워져 있으면 좋습니다. 1번 인덱스부터 계산을 해나가면서 1번 인덱스 이전의 상태를 참고해야할 일이 있을 때, 0번 인덱스를 이용할 수 있다면 따로 인덱스 범위 계산을 할 필요 없이, 0번 인덱스가 1번 이전의 디폴트 상태라고 생각하고 문제를 풀 수 있기 때문입니다. 

 

아래 풀이를 보면, dp[i] > dp[j - 1] + 1 이라는 부분이 있는데요. 이 때 올 수 있는 j범위가 1부터 i까지입니다. 하지만 j - 1을 접근하는 것을 볼 수 있습니다. 만약 0번 인덱스부터 시작했다면 이 경우는 j - 1에 접근할 수 없으니 분기 처리를 해줘야 했겠죠?

 

dp 배열은 무엇을 담고 있을까요? index 까지를 표현하는 분할의 최소 방법의 수를 담고 있습니다. 

예제로 주어진 ABACABA 를 보도록 하겠습니다.

 

i = 1, j = 1 -> isPalindrome(j, i): true / dp[1] = dp[0] + 1 = 1

i = 2, j = 1 -> isPalindrome(j, i): false / dp[2] = dp[1] + 1 = 2

i = 2, j = 2 -> isPalindrome(j, i): false

i = 3, j = 1 -> isPalindrome(j, i): true / dp[3] = dp[0] + 1 = 1

.

.

.

 

어떤 식으로 계산이 이루어지는지 보이죠? 해당 범위가 팰린드롬일 경우, 그 범위 이전의 최솟값 + 1이 현재 dp 배열에 저장되어 있는 값보다 작을 경우/아직 저장된 값이 없을 경우 교체하는 방식으로 계산을 진행하게 됩니다.

#include <iostream>
#include <string>
using namespace std;

string str;
int pal[2501][2501];
int dp[2501];

int isPalindrome(int s, int e) {
    if (pal[s][e] != -1) {
        return pal[s][e];
    }

    if (s == e) {
        return pal[s][e] = 1;
    }
    
    if (s == e - 1) {
        return str[s] == str[e] ? pal[s][e] = 1 : pal[s][e] = 0;
    }
    
    return str[s] == str[e] ? pal[s][e] = isPalindrome(s + 1, e - 1) : pal[s][e] = 0;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> str;
    int len = str.size();
    str = " " + str;

    for (int i = 1; i <= len; i++) {
        dp[i] = -1;
        for (int j = 1; j <= len; j++) {
            pal[i][j] = -1;
        }
    }

    dp[0] = 0;
    for (int i = 1; i <= len; i++) {
        for (int j = 1; j <= i; j++) {
            if (isPalindrome(j, i)) {
                if (dp[i] == -1 || dp[i] > dp[j - 1] + 1) {
                    dp[i] = dp[j - 1] + 1;
                }
            }
        }
    }
    cout << dp[len] << '\n';

    return 0;
}