BOJ 13361 - 최고인 대장장이 토르비욘

문제 링크 : www.acmicpc.net/problem/13361

문제 풀이

이 문제를 풀기 위해서는 아주 간단하지만 핵심적인 관점 바꾸기를 하나 해야한다. '뒤집어서 생각하기' 우리가 구하고자 하는 것은 가장 긴 세로의 길이의 합이다. 근데 이는 전체에서 가장 짧은 가로 길이의 합을 뺀 것과 같다.

만약 이 문제가 같은 길이로도 이어 붙일 수 있었으면 어땠을까? 굉장히 쉬운 문제가 되었을 것이다. 그냥 모든 판을 길이가 짧은 쪽을 가로로 돌린다. 임의의 정수 집합은 같거나 작아지는 순서대로 배치 할 수 있기 때문에 항상 작은 쪽을 가로로 선택해도 조건에 맞게 해결을 할 수 있게 된다. 

하지만 본 문제에서는 같은 길이도 선택을 할 수 가 없다. 이 부분이 핵심이고, 따라서 판들을 같은 길이가 존재하는 지의 여부로 묶어준다. 
즉 (30000,50000), (50000,100000), (30000, 120000) 짜리의 판 3개가 있다면 이 3개의 판을 모두 한 세트로 묶어주는 것이다. 이렇게 묶어주면 3개의 판에 대해서 선택할 수 있는 변의 길이는 (30000,50000,100000,120000) 으로 4종류가 나오게 되고, 이 중에서 가장 작은 3가지 변의 길이를 선택하는 것이 최솟값이며, 이 경우를 각 판이 하나씩 담당하게 무조건 만들 수 있다. 

즉, union&find 를 이용하여 같은 길이의 존재 여부로 판 들을 그룹으로 묶어주고, 그 그룹내에 존재하는 변의 길이의 모든 종류 중에서 가장 작은 k개의 길이 (이때 k는 그룹에 속한 판의 수) 를 선택해서 전체 값에서 빼주는 것을 모든 그룹에 대해서 반복하면 이 문제를 해결할 수 가 있게 된다. 

아이디어가 굉장히 놀라웠던 문제이다. 

코드

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> pii;
#define eb emplace_back
#define pb push_back
#define ff first
#define ss second
 
pii arr[1010101];
vector<pii> poi;
 
ll par[1010101];
ll sz[1010101];
vector<ll> gp[1010101];
 
vector<ll> loc;
 
ll fi(ll x){
    if(x==par[x]) return x;
    return par[x]=fi(par[x]);}
 
void uf(ll a,ll b){
    a=fi(a);
    b=fi(b);
    if(sz[b]<sz[a]){
        par[b]=a;
        sz[a]+=sz[b];
    }
    else{
        par[a]=b;
        sz[b]+=sz[a];
    }
 
}
 
int main(){
    ll i,j,k,l,m,n;
    ll ans=0;
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    cin>>n;
    for(i=1;i<=n;i++){
        cin>>arr[i].ff>>arr[i].ss;
        poi.eb(arr[i].ff,i);
        poi.eb(arr[i].ss,i);
        ans+=arr[i].ff;
        ans+=arr[i].ss;
        par[i]=i;
        sz[i]=1;
    }
 
 
    sort(poi.begin(),poi.end());
 
    for(i=1;i<poi.size();i++)
        if(poi[i].ff==poi[i-1].ff&&fi(poi[i].ss)!=fi(poi[i-1].ss))
            uf(poi[i].ss,poi[i-1].ss);
    
    for(i=1;i<=n;i++)
        gp[fi(i)].pb(i);
 
    for(i=1;i<=n;i++){
        loc.clear();
        ll cnt=gp[i].size();
        if(cnt==0) continue;
        for(auto k:gp[i]){
            loc.pb(arr[k].ff);
            loc.pb(arr[k].ss);
        }
        sort(loc.begin(),loc.end());
        loc.erase(unique(loc.begin(), loc.end()),loc.end());
        for(j=0;j<cnt;j++){
            ans-=loc[j];
        }
    }
    cout<<ans;
 
}