[ICPC] 백준 2135 - 문자열 압축하기

www.acmicpc.net/problem/2135

 

다음 dp테이블을 정의한다.

 

dp[i][j] := i번째부터 j번째까지 부분 문자열을 압축한 길이

 

문자열을 얼마나 압축이 가능한지 파악하기 위해 문자열을 압축할 구간의 길이에 대해 반복문을 돌린다.

 

문자열을 압축할 수 있는 모든 경우를 탐색하기 위해 해당 길이의 진약수를 모두 구하여 저장한다.

 

이 진약수들에 대해 반복문을 돌려 구간 내 문자열들이 진약수를 길이로 가지는 부분 문자열들로 압축이 가능한지 확인한다.

 

예를 들어 길이가 8인 "gogogogo"를 압축한다고 하고 8의 진약수 중 2에 대해 계산하면 "gogogogo"에서 길이 2의 부분 문자열은 "go"가 되므로 부분 문자열로 압축할 수 있음을 확인할 수 있다.

 

만약 압축이 가능하면 부분 문자열을 압축한 길이를 갱신한다.

 

구현 소스를 참조하면 변수 compressed가 압축한 길이이고 그 초기값으로 압축할 구간의 길이가 들어있다.

 

진약수들에 대해 구간의 압축을 끝내면 한 구간으로 압축한 길이와 두 구간으로 나눠 압축한 길이를 더한 것을 비교하여 최종 압축 길이를 저장한다.

 

전체 코드

#include <bits/stdc++.h>
 
using namespace std;
 
string s;
int n;
int dp[201][201];
 
vector<int> get_proper_div(int num);
bool can_compress(int start, int end, int segment);
int get_length(int num);
 
int main()
{
    cin.tie(0); ios::sync_with_stdio(false);
    cin >> s;
    n = s.size();
 
    for (int i = 0; i < s.size(); ++i)
        dp[i][i + 1] = 1;
    
    for (int i = 2; i <= n; ++i)
    {
        vector<int> divs = get_proper_div(i);
        
        for (int stt = 0; stt <= n - i; ++stt)
        {
            int compressed = i;
 
            for (auto item: divs)
                if (can_compress(stt, stt + i, item))
                    compressed = min(compressed, 2 + dp[stt][stt + item] + get_length(i / item));
 
            for (int j = stt + 1; j < i + stt; ++j)
                compressed = min(compressed, dp[stt][j] + dp[j][i + stt]);
 
            dp[stt][stt + i] = compressed;
        }
    }
 
    cout << dp[0][n];
}
 
vector<int> get_proper_div(int num)
{
    vector<int> ret;
 
    for (int i = 1; i < num; ++i)
        if (!(num % i))
            ret.push_back(i);
 
    return ret;
}
 
bool can_compress(int start, int end, int segment)
{
    for (int i = start; i < end; i += segment)
        if (s.substr(start, segment) != s.substr(i, segment))
            return false;
    return true;
}
 
int get_length(int num)
{
    int pivot = 1, ret = 0;
 
    while (num / pivot)
        pivot *= 10, ++ret;
 
    return ret;
}