BOJ 3681번 모빌

문제 링크

이 문제는 일단 모빌이 주어진다. 모빌이란, 막대기가 있고 막대기의 양쪽에 모빌또는 물체가 달린다.

모빌의 깊이는 최대 16이다.  이때 각 모든 막대기의 양옆에 달린 덩어리 두개가 균형을 이루게 만들기 위해

최소 몇개의 물체나 무게를 변경해야 하는지 구하는 문제이다.

예를들어,

이런 모빌이 있다면 7을 3으로 만들면 모든 막대기에서 균형이 맞게되므로 답은 1이다.

3을 7로, 6을 14로 바꿔도 균형을 이루지만 최소의 개수가 아니기 때문에 답이 아니다.

그러면 결국 전체 모빌의 무게를 x로 만들려고 할때 각 덩어리의 무게는 다음과 같이 만들어 주어야 한다.

그렇다면 x를 정해주고 재귀적으로 따라 내려가면서 각각의 덩어리에 대해 되어야 하는 무게와 현재 물체의 무게가

같다면 바꾸어 주어야하는 것이기 때문에 다를 때 cnt++ 을 해주어 몇개의 물체나 무게를 변경해 주어야하는지

계산할 수 있기 때문에 이 행위를 모든 가능한 x 에 대해 계산하여 최소값을 구하면 된다.

하지만 가능한 모든 x가 너무 많기 때문에 다 봐주면 시간안에 돌아갈 수가 없다. 그럼 어떻게 할까?

한 번 반대로 생각해 보자. 모든 각각의 물체에 대해 현재 무게를 그대로 유지하기 위하여 전체무게를 무엇으로

잡아야 하는지를 보는 것이다. 이렇게 생각하면 이해가 쉬울 것같다. 각각의 물체들이 살아 움직이는 생명체인데

각각의 물체들은 자신의 현재 몸무게를 사랑해서 절대로 무게를 바꾸기 싫어한다. 그래서 자신의 무게를 바꾸지 않아도

되게 해주는 전체 무게를 선발하기위해 투표를 한다. 각 물체는 투표권이 하나씩있으며 최대한 많은 물체의

욕구를 만족시켜주는 전체무게가 답이되기 때문에 가장많이 투표를 받은 전체무게가 최종적으로 선발된다.

그리고 각각의 물체에 대해 무게가 바뀌지 않기위한 전체 무게는 현재무게*(2^depth) 가 되기때문에 

전체 무게에 투표를 하는 행위를 STL map 에서 투표 대상을 key로 하고 value를 투표수로 하면 map[x]++ 식으로

하면 되기 때문에 하나의 물체가 투표를 하는데에는 O(lgN) 의 시간이 걸린다. (N은 전체 물체의 수)

그렇기 때문에 모든 물체에 대해 투표를 하게 하면 O(NlgN) 의 시간이 걸리며

깊이가 최대 16이기때문에 물체는 최대 O(N)개가 된다. 그렇기 때문에 1표이상 받은 후보는 최대 O(N)개

이기 떄문에 가장 많은 득표수를 얻은 후보를 고르는데에는 O(N)의 시간이 걸린다.

그럼 가장 득표수가 많은 무게의 득표수를 전체 물체의 수에서 빼면 욕구가 만족되지 않은 물체의 수가 나오게 되고

이 것이 바로 무게를 바꿔줘야할 최소의 물체의 수가 된다. 

#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9+7;
const int INF = 0x3c3c3c3c;
const long long INFL = 0x3c3c3c3c3c3c3c3c;
 
map<long long,int> mp;
int cnt;
 
void go(string str, int depth){
    int st = 0;
    int sec = 0;
    int i;
    for(i = 0 ; i < str.size(); i++){
        if(str[i] == '[') st++;
        else if(str[i] == ']') st--;
        if(!sec && st == 1) sec = 1;
        else if(sec && st == 1 && str[i] == ',') break; 
    }
    if(i == str.size()){
        long long num = stol(str);
        mp[num<<depth]++;
        cnt++;
        return;
    }
    go(str.substr(1, i - 1), depth+1);
    go(str.substr(i+1, str.size() - 2 - i), depth+1);
}
int main() {
    int T;
    scanf("%d",&T);
    while(T--){
        mp.clear();
        string str;
        cin >> str;
        cnt = 0;
        go(str, 0);
        int ans = INF;
        for(auto it = mp.begin(); it != mp.end(); it++){
            ans = min(ans, cnt - (*it).second);
        }
        printf("%d\n",ans);
    }
 
    return 0;
}