백준 1509번

오늘 풀어본 문제는 백준의 1509번 문제¹이다. 문제 풀이에 사용한 언어는 C++ 이다.

solved.ac 기준 CLASS

CLASS 5

문제 정보

이 문제의 내용과 조건은 다음과 같다.

문제

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

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

입력

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

출력

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

풀이과정

1번째 시도

문제를 보고 DP 문제라는 것을 알 수 있었다. 결국 찾아낸 해결 방식은 다음과 같다.

checkPalindrome 이라는 2차원 배열을 만들어 각 부분 문자열들이 회문인지를 저장한다.
dp 1차원 배열을 만들어 첫 번째 문자부터 해당 인덱스의 문자까지의 부분문자열이 최소 몇 개의 회문으로 분할 가능한지 저장한다. 점화식은 다음과 같다.

$dp[n] = \min (dp[k_1 - 1] + 1, dp[k_2 - 1] + 1, \cdots)$

이 때 $k_m$ 번째 인덱스 부터 $n$ 번째 인덱스 까지의 부분문자열은 회문을 이룬다.
dp 배열의 마지막 인덱스에 저장 된 값이 우리가 구하고자 하는 정답이 된다.

코드는 다음과 같이 작성하였다.

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using ull = unsigned long long;
using pll = pair<ll, ll>;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    string input;
    cin >> input;

    ull len = input.length();

    vector<vector<bool>> checkPalindrome(len, vector<bool>(len, false));
    vector<int> dp(len, INT_MAX);

    for (int i=0; i<len; i++) {
        checkPalindrome[i][i] = true;
    }
    for (int i=0; i<len-1; i++) {
        if (input[i] == input[i+1]) {
            checkPalindrome[i][i+1] = true;
        }
    }
    for (int subLen=3; subLen<=len; subLen++) {
        for (int i=0; i<len-subLen+1; i++) {
            if (input[i] == input[i+subLen-1] && checkPalindrome[i+1][i+subLen-2]) {
                checkPalindrome[i][i+subLen-1] = true;
            }
        }
    }

    dp[0] = 1;
    for (int end=1; end<len; end++) {
        for (int begin=0; begin<=end; begin++) {
            if (checkPalindrome[begin][end]) {
                if (begin == 0) {
                    dp[end] = 1;
                }
                else {
                    dp[end] = min(dp[end], dp[begin-1] + 1);
                }
            }
        }
    }

    cout << dp[len - 1];

    return 0;
}

그러자 모든 테스트 케이스를 통과하고 ‘맞았습니다’가 나오는 것을 확인할 수 있었다.

마무리

DP 문제는 언제 풀어도 어려운 것 같다. 최적의 해를 부분 문제들의 해를 이용하여 구성한다는 기본적인 아이디어까지는 알겠는데, 상황이 너무 다양하고, 시간 초과라던가 항상 걱정이 되어서 자신있게 문제를 풀어본 적이 없는 것 같다.

어쩌면 PS 수련은 단순히 CLASS 문제 미는 것이 다가 아니라, DP 문제들을 많이 풀어보는 것이 중요한 것일까? 그래서 사람들이 골랜디 (골드 랜덤 디펜스) 라던가 그런걸 하는 것일까? 조만간 나도 해야할지도 모르겠다…

오늘의 PS는 여기까지!

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

← Previous Post Next Post →