[Baekjoon - 2471] 모빌 이진수

난이도: Platinum II

 

태그

• Stack → Parenthesis Matching
• Dynamic Programming (on Tree) → Kth Smallest Element
• (Ordered) Set
• Backtracking

 

풀이

1. 괄호 문자열을 토대로 트리를 만들어보자.

각각의 괄호 쌍에 대해, 이 안에 있는 다른 괄호 쌍이나 숫자를 이어줍시다.

 

그러니까... 대강 이런 식으로요.

 

하나의 괄호 쌍은, 자식으로 다른 괄호 쌍이나 어떤 수를 가지게 됩니다.

그럼, 특정 괄호 쌍을 나타내는 정점에서 만들 수 있는 문자열은, 각 자식에서 만들 수 있는 문자열을 들고 온 뒤, 그 순서대로 concat하는 것으로 볼 수 있겠죠.

 

또한, 이렇게 트리를 만들면, ()를 뒤집는 건 그 서브트리 전체를 뒤집는 것으로 생각할 수 있습니다.

 

2. 트리의 특정 정점에서 만들 수 있는 문자열은?

\( dp_{v} \) = 정점 \( v \)를 루트로 하는 서브트리에서 만들 수 있는 문자열들의 집합 이라고 잡아봅시다.

 

만약 정점 \( v \)가 숫자 1개만을 들고 있다면 (리프 노드), \( dp_{v} \)는 그냥 그 숫자가 됩니다.

 

그럼, 남은 건 괄호 쌍을 나타내는 정점이네요.

이는, \( w \in \text{child}(v) \)들에 대해, 각각의 \( dp_{w} \)에서 만들 수 있는 문자열 중 하나를 골라서 이은 것으로 생각할 수 있습니다.

 

즉, \( dp_{v} = (\sum\limits_{w \in \text{child}(v)} dp_{w}) \cup \text{reverse}(\sum\limits_{w \in \text{child}(v)} dp_{w}) \)라고 볼 수 있죠.

// 편의상, 두 문자열의 concat을 \( s_1 + s_2 \)라고 표현합시다.

// 또한, \( \text{reverse}(S) = \{ \text{rev}(s) | s \in S \} \)라고 합시다.

// 여기서 \( \text{rev}(s) \)는 \( s \)를 뒤집은 문자열을 의미합니다.

 

그런데, \( \text{reverse}(\sum\limits_{w \in \text{child}(v)} dp_{w}) = \sum\limits_{w \in \text{child}(v) \text{ in reverse order}} \text{reverse}(dp_{w}) \)입니다.

그리고, \( \text{reverse}(dp_{w}) = dp_{w} \)입니다.

// 점화식을 생각해보면, 자명하죠. \( dp_{w} \) 자체가 정방향과 역방향을 동시에 담고 있으니까요.

 

즉, 점화식을 조금 더 간단하게 적으면 \( dp_{v} = (\sum\limits_{w \in \text{child}(v)} dp_{w}) \cup (\sum\limits_{w \in \text{child}(v) \text{ in reverse order}} dp_{w}) \) 가 됩니다.

 

3. 문제의 답은?

문제의 답은, 루트 정점에서 \( K \)번째로 작은 문자열이 됩니다.

 

4. 구현 디테일

당연하겠지만, \( dp_{v} \)에 모든 문자열을 저장할 수는 없습니다.

대신에, \( dp_{v} \)에서 가장 작은 \( K \)개의 문자열만 저장한다면?

 

사전순 최소의 조건 때문에 \( dp \)를 계산할 때에도 작은 문자열부터 사용하는 것이 이득이므로, 시간/공간 복잡도에 큰 이득을 가져다주게 됩니다.

 

5. 코드

string s; int k;
vector<int> adj[220];
 
set<string> dp[220];
set<string> res; string str; int cnt = 0;
void btk(const int now, int idx, int dir){
    //cout << "BTK " << now << ' ' << idx << ' ' << dir << ' ' << cnt << ' ' << str << endl;
    if (idx == adj[now].size() || idx == -1){
        res.insert(str); cnt += 1;
        return;
    }
    int nxt = adj[now][idx];
    for (string t : dp[nxt]){
        int tl = t.size();
        for (int i = 0; i < tl; i++){ str.push_back(t[i]); }
        btk(now, idx+dir, dir); if (cnt == k){ return; }
        for (int i = 0; i < tl; i++){ str.pop_back(); }
    }
}
set<string> dpf(int now){
    if (!dp[now].empty()){ return dp[now]; }
    int m = adj[now].size();
    if (m == 0){
        set<string> res; res.insert( string(1, s[now]) );
        //for (string s : res){ cout << "DP " << now << " = " << s << endl; }
        return dp[now] = res;
    }
    for (int nxt : adj[now]){ dpf(nxt); }
    res.clear();
    str = ""; cnt = 0; btk(now, 0, +1);
    str = ""; cnt = 0; btk(now, m-1, -1);
    while (res.size() > k){ res.erase( prev(res.end()) ); }
    //for (string s : res){ cout << "DP " << now << " = " << s << endl; }
    return dp[now] = res;
}
 
void Main(){
    cin >> s >> k; int sl = s.size();
    stack<pci> stk;
    for (int i = 0; i < sl; i++){
        char ch = s[i];
        if (ch == '0' || ch == '1' || ch == '('){ stk.push({ch, i}); }
        if (ch == ')'){
            vector<int> v;
            while (!stk.empty()){
                pci p = stk.top(); stk.pop();
                if (p.fr == '('){ adj[p.sc] = v; stk.push({'.', p.sc}); break; }
                else{ v.push_back(p.sc); }
            }
        }
    }
    /*for (int i = 0; i < sl; i++){
        for (int j : adj[i]){ cout << "ADJ " << i << ' ' << j << endl; }
    }*/
    set<string> res = dpf(0);
    if (res.size() < k){ cout << "NO"; }
    else{ cout << *prev( res.end() ); }
}