[백준/C++] 1509 - 팰린드롬 분할

풀이 시간: 2h19m12s02

시간 복잡도: O(N^2)

공간 복잡도: O(N^2)

참고 자료

https://hyeo-noo.tistory.com/137
https://yabmoons.tistory.com/592

문제

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

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

입력

첫째 줄에 문자열이 주어진다. 이 문자열은 알파벳 대문자로만 이루어져 있고, 최대 길이는 2,500이다.

출력

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

문제 풀이

원래도 DP는 잘 못풀었지만, 도무지 이 문제는 아이디어가 떠오르지 않았다.

그래서 1시간 정도 고민 끝에 그냥 참고 코드를 보기로 했다.

참고 코드를 보고 느낀 건, 어떻게 이런 발상을 했지 싶기도 하고 어차피 3시간 줘도 못풀었겠다 싶었다.

DP 접근법도 아직 제대로 숙지하지 못했고, 이 문제는 특히 좀 어려웠다고 생각했다.

 

우선 필요한 변수들을 정의해주었다.

string str: 문자열

int N: 문자열의 길이

int ans[i]: 맨 처음부터 i번째 문자열까지 탐색했을 때까지의 팰린드롬 분할 개수의 최솟값

bool dp[i][j]: i번째부터 j번째까지가 하나의 팰린드롬인 경우 true, 아닌 경우 false

 

문제는 다음과 같이 접근했다.

 

1. setDP() 함수를 통해 dp 배열 값들을 전부 설정

2. setAns() 함수를 통해 팰린드롬 분할 개수의 최솟값 찾기(출력할 값 찾기)

 

setDP() 함수에서는 우선적으로 dp 배열의 값들을 전부 설정해주었다.

앞서 말했듯이, dp 배열에는 특정 구간에서의 팰린드롬 여부를 체크하는 함수이다.

 

따라서, 문자열에서 각 문자 하나하나는 dp가 true일 수밖에 없다. 코드로 나타내면 다음과 같이 된다.

dp[i][i] = true;

 

그리고, 문자열에서 문자열 길이를 2로 분할했을 경우, 즉 "AB", "CD" 이런 경우에도 특징이 있는데, 두 문자가 서로 같아야 팰린드롬이 된다는 것이다. 따라서 다음과 같은 경우가 될 수 있다.

"AA", "BB", "CC", "DD", ...

이 부분의 코드는 다음과 같이 나타낼 수 있다. 주어진 처음과 끝, 즉 앞뒤 문자가 서로 동일하고, 해당 문자의 인덱스의 차이가 1인 경우(문자열이 서로 옆에 붙어있는 경우를 뜻한다.) dp를 true로 설정할 수 있겠다.

if (str[start] == str[end] || end - start == 1) return true;

 

마지막으로, 문자가 3개 이상인 경우를 고려해볼 수 있는데, 우선 위에서는 문자가 1개, 2개인 경우의 dp를 설정해두었다.

여기서 저장한 값들을 토대로 메모이제이션 기법을 활용하여 문자가 3개 이상인 경우에 팰린드롬인지 확인할 수 있다.

 

문자가 3개 이상인 경우에는, 일단 처음과 끝의 문자가 서로 동일해야한다.

그리고, 남은 부분은 처음과 끝을 제외한 나머지 부분을 의미하는데 해당 부분의 dp값이 true이면 되는 것이다.

if (str[start] == str[end] && dp[start + 1][end - 1]) return true;

아래 코드처럼, dp는 Bottom-up 방식을 사용하여 작은 수부터, 즉 문자열 길이가 짧은 것부터 차례대로 값을 설정해나갈 것이기 때문에 이전 값들이 모두 저장이 되고, 이를 사용해 문자열 길이가 더 긴 문자열의 팰린드롬 여부를 확인할 수 있는 것이다.

for (int dis = 0; dis < N; ++dis) { // 문자열 길이
    for (int i = 1; i + dis <= N; ++i) {
    	if (dis == 0) dp[i][i] = true; // 각각의 문자 하나하나는 모두 팰린드롬
        else if (isPal(i, i + dis)) dp[i][i + dis] = true;
        // i번째 문자부터 (i + dis)번째 문자까지가 하나의 팰린드롬일 경우 dp는 true
    }
}

 

그렇게 dp 값을 모두 저장하고 나면 dp 배열을 사용하여 출력할 값, 즉 팰린드롬 분할 개수의 최솟값을 저장해주어야 한다.

우선, 초기에 선언한 ans[] 배열을 전부 무한대로 초기화해준다. 이 작업을 해주는 이유는 이제부터 dp 값과 비교하여 더 작은 값으로 갱신해줄 것이기 때문이다.

 

갱신 규칙은 다음과 같다.

1. 마지막 문자(ed)를 문자열 끝(N)까지, 처음 문자(st)를 마지막 문자(ed)까지 이중 for문으로 구현하여 모든 dp를 순회한다.

2. 처음 문자(st)부터 마지막 문자(ed)까지의 dp값이 true인 경우, 해당 길이의 문자가 하나의 팰린드롬이므로, 이때만 ans 값을 갱신해준다.

ans[ed]: 처음부터 ed번째 문자까지를 탐색했을 때 구한 최소 팰린드롬 분할 수

ans[st - 1] + 1: 이전까지의 문자열의 최소 팰린드롬 분할 수 + 현재 문자 1

여기서 "ans[st - 1] + 1"를 해주는 이유는, dp에서 true를 발견했을 경우, 해당 문자까지 하나의 팰린드롬이 발견된 것이기 때문에 이전 문자까지 구한 최소 팰린드롬 분할 수에 1을 더하여 지금 발견한 팰린드롬 하나를 더해주는 것이다.

void setAns() {
    ans[0] = 0;
    for (int ed = 1; ed <= N; ++ed) {
        ans[ed] = INF;
        for (int st = 1; st <= ed; ++st) {
            if (dp[st][ed]) ans[ed] = min(ans[ed], ans[st - 1] + 1);
        }
    }
}

전체 코드

#include <iostream>
#include <string>
#define MAX 2501
#define INF 1e9
using namespace std;
string str;
int N, ans[MAX];
bool dp[MAX][MAX];

bool isPal(int start, int end) {
    if (str[start] == str[end] && (dp[start + 1][end - 1] || end - start == 1)) return true;
    return false;
}

void setDP() {
    for (int dis = 0; dis < N; ++dis) {
        for (int i = 1; i + dis <= N; ++i) {
            if (dis == 0) dp[i][i] = true;
            else if (isPal(i, i + dis)) dp[i][i + dis] = true;
        }
    }
}

void setAns() {
    ans[0] = 0;
    for (int ed = 1; ed <= N; ++ed) {
        ans[ed] = INF;
        for (int st = 1; st <= ed; ++st) {
            if (dp[st][ed]) ans[ed] = min(ans[ed], ans[st - 1] + 1);
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> str;
    N = str.size();
    str = " " + str; // 문자열 인덱스 1부터 시작하도록 맞춰줌
    setDP(); setAns();
    cout << ans[N];
    return 0;
}

 

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

1509번: 팰린드롬 분할