BOJ 1509 : 팰린드롬 분할

3줄 요약:

• DP

 

난 도대체 왜 팰린드롬을 분할하는 것인지 모르겠다. 어느 문제에서는 유사회문인지를 출력하라 하지 않나, 어느 문제에서는 공장을 개설하지 않나... 팰린드롬은 내가 제일 싫어하는 문제 중 하나이다.

 

 

이 문제를 풀 때는 DP를 두 번 사용하여 풀 수 있다.

• dp[i][j] = i번째 문자부터 j번째 문자까지 회문인지 체크하는 dp
• dp2[i] = i번째 인덱스에서 분할 개수의 최솟값

 

dp[i][j]가 약간 이해가 안 갈 수 있는데, 예를 들어보자.

 

문자열 'BOTTOM' 에서 제일 앞의 인덱스를 1이라고 할 때, dp[1][6]은 false이고, dp[2][5]는 true, dp[3][4]도 true... 이렇게 볼 수 있다. 이를 어떻게 구현할까?

 

dp[i][j] 가 true이고, str[i - 1] == str[j + 1] 이라면, dp[i - 1][j + 1] 또한 true라는 점을 이용하여 dp 테이블을 Bottom-Up 방식으로 채울 수 있다.

 

마찬가지로 dp2를 구현하는 방법을 알아보자. idx번째 인덱스에서 다음과 같은 행동을 취할 수 있다. (idx = 현재 인덱스)

 

solve(idx) 에 대해 i = idx보다 크거나 같은 모든 인덱스일 때,

dp[idx][i] = true 라면, dp2[idx] = min(dp2[idx], solve(i + 1) + 1)

 

볼 수 있듯이 이는 Top-Down 방식으로 구현해야 한다. 이로써 모든 설명은 끝났다. 코드는 밑에 있다.

 

 

#include <iostream>
#include <string>

using namespace std;

bool dp[2501][2501];
int dp2[2501];

int sz; char str[2501];

int solve(int idx) {
    if (dp2[idx] != -1) return dp2[idx];
    int ans = 99996974;
    for (int i = idx; i <= sz; i++) {
        if (dp[idx][i]) ans = min(solve(i + 1) + 1, ans);
    }
    return dp2[idx] = ans;
}

int main() {

    string s; cin >> s;
    sz = s.size();
    for (int i = 0; i < sz; i++) {
        str[i + 1] = s[i];
    }

    str[sz + 1] = '0';
    for (int i = 1; i <= sz; i++) {
        dp[i][i] = true;
        if (str[i] == str[i + 1]) dp[i][i + 1] = true;
    }

    for (int i = 1; i <= sz; i++) {
        for (int j = 1; j <= sz; j++) {
            int s = i, r = j;
            while (str[s - 1] == str[r + 1] && dp[s][r]) {
                dp[s - 1][r + 1] = true;
                s--; r++;
            }
        }
    }

    for (int i = 1; i <= sz; i++) {
        dp2[i] = -1;
    }

    cout << solve(1) << endl;
}

 

 

난이도(객관적): Gold I

난이도(개인적): Gold I