[백준 20967] Uddered but not Herd

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

20967번: Uddered but not Herd

USACO 2021 January Contest > Gold 1번으로 출제된 문제이다.

---

풀이

제한을 자세히 읽어보면 가능한 문자 종류 개수는 최대 20개라는 것을 알 수 있다. 또한 아래와 같이 문제를 다르게 말할 수도 있다는 것도 관찰할 수 있다:

주어진 문자열을 조각으로 분할하되, 각 조각 내에 있는 문자들이 cowphabet order를 준수하도록 하는 가장 적은 횟수의 분할을 찾아라.

만약에 cowphabet order가 주어졌다고 생각해보자. 그러면:

• "입력 문자열 내의 인접한 character pair가 주어진 cowphabet order를 위반하는 경우"에만 그 character pair 사이를 분할하면 충분하다는 것을 알 수 있다.
• 이를 통해, 추가적으로 문제를 "주어진 문자열 내에서 cowphabet order를 위반하는 character pair의 갯수를 세는 문제"로 바꿀 수도 있다.

(원래 문제로 돌아와서) 그러면 우리는 cowphabet order 위반을 최소로 만드는 cowphabet order를 찾으면 문제가 해결된다는 걸 알 수 있다. 모든 cowphabet order를 하나하나 순회할려면 당연히 시간초과가 나겠지만, cowphabet order의 character를 순서대로 하나하나 추가해간다는 식으로 접근하면 bitmask dp로 시간제약 내에 구현할 수 있다. 상태값을 "지금까지 cowphabet order에 사용한 character의 bitmask", dp값을 "cowphabet order 위반 개수"로 잡으면, 상태에 새롭게 character를 추가할 때 [새로운 character] - [기존에 상태에 있던 character] 순서의 위반 pair만 dp값에 추가해주면 된다.

 

http://www.usaco.org/current/data/sol_prob1_gold_jan21.html 에서 구체적인 수식과 함께 더 잘 설명해주고 있다.

#include <bits/stdc++.h>
using namespace std;
#define int long long

int pair_count[20][20];
int32_t main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    string s;
    cin >> s;
    map<char, int> mp;
    for(char c: s)
        mp[c] = 0;
    int chars = 0;
    for(auto &pr: mp)
        pr.second = chars++;
    for(int i = 1; i < s.size(); i++) {
        pair_count[mp[s[i - 1]]][mp[s[i]]]++;
    }
    vector<int> bitmasks;
    for(int i = 1; i < (1 << chars); i++) {
        bitmasks.push_back(i);
    }
    sort(bitmasks.begin(), bitmasks.end(), [](int a, int b) {
        return __builtin_popcount(a) < __builtin_popcount(b);
    });
    vector<int> dp(1 << chars);
    for(auto bm: bitmasks) {
        dp[bm] = 1e18;
        for(int i = 0; i < chars; i++) {
            if(bm & (1 << i)) {
                int tmp = dp[bm ^ (1 << i)];
                for(int j = 0; j < chars; j++) {
                    if(bm & (1 << j)) {
                        tmp += pair_count[i][j];
                    }
                }
                dp[bm] = min(dp[bm], tmp);
            }
        }
    }
    cout << dp[(1 << chars) - 1] + 1;
}