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

난이도 : Solved.ac 기준 다이아 5

출처 : ICPC NWERC Regional, Nordic Collegiate Programming Contest [NCPC] 2016 H

 

1. 문제 설명

직사각형 $n$ 개가 주어진다. 각각의 두 변의 길이는 $a_i, b_i$ 이고, 이걸 적당히 돌려서 $n$개를 위로 쌓으려고 한다.

다음 조건을 만족해야 한다.

- 각 직사각형의 '너비' 는 Strictly 감소 수열을 이뤄야 한다. 

- 가능한 경우 중 '높이' 가 최대한 커야 한다.

 

 

2. 풀이 

굉장히 중요한 발상이 있는데, 이 발상을 처음 떠올리기는 많이 힘든 것 같다. 비슷한 문제를 어디선가 누가 말해줘서 이런 생각을 본적이 있는데 출처를 모르겠다. :( 

직사각형이 가진 두 숫자 $a_i$ 와 $b_i$ 를 정점으로, 직사각형의 존재를 간선으로 갖는 그래프를 그리자. 일단은 Undirected Graph이면서, Multiple edge를 허용하기로 하자.

이때, 여러 번 등장하는 숫자는 하나로 합쳤으므로, 한 정점을 여러 번 '너비' 로 쓸 수 없다는 조건을 주면, 여러 정점들 간에는 distinct하므로 순서대로 정렬해서 찍어주면 된다. 따라서, 주어진 문제는 다음과 같다.

"Undirected graph가 주어진다. 이제, 여기에 각 Edge의 방향을 주어서, 각 정점의 out-degree가 1을 넘지 않게 하자"

이때, 우리는 각 직사각형의 "너비에서 나와서", "높이로 들어가는" 간선을 만들어주는 셈이므로, 우리가 구하려는 최대 높이는 다음과 같이 나타낼 수 있다.

$$H = \sum val(v) \cdot indeg(v) $$ 

 

그런데, 실제로 이 그래프에 간선 방향을 지정해주는 것은 쉽지 않은 일이다. 임의의 그래프에 저렇게 간선 방향을 주려고 생각하는 대신, 원래의 문제로부터 유용한 성질을 더 가지고 오자. 하나의 Connected component만 볼 때, 각 정점에서 나오는 out degree가 최대 1이라고 주어졌으므로, $V < E$ 이면 절대 방향을 잘 줄 수 없다. 따라서 $V \geq E$ 이고, Connected graph가 (Connected Component 만 보기로 했으므로 그 Component는 Connected Graph) 그런 조건을 만족하려면 트리이거나 트리+1 ($V = E$) 여야 한다.

 

만약 주어진 그래프가 트리가 아니라면, 모든 점은 outdegree가 1이다. 또한, 방향을 주긴 어려워도 Undirected graph modeling은 어렵지 않으므로, 각 정점의 degree는 쉽게 알 수 있다. 그러면, indegree = degree - outdegree로 두고, 

$$H = \sum val(v) \cdot (deg(v)-1) $$ 이와 같이 쉽게 구할 수 있다.

 

만약 주어진 그래프가 트리라면, 모든 점의 Outdegree가 최대 1이라는 조건으로부터, 딱 하나의 정점은 Outdegree가 0이라는 조건을 알 수 있다. Outdegree가 0이 된다면, 위 식에 정점값 하나는 한번 더 더해진 형태, 즉 $$H = \sum val(v) \cdot (deg(v)-1)  + val(v_0)$$와 같이 나타날 것이다. $H$를 최대화하려는 목표를 가지고 있으므로, 가장 값이 큰 정점을 고르면 해결.

 

 

3. 코드

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define usecppio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define all(x) ((x).begin()),((x).end())
#define int ll
using pii = pair <int, int>;
#define INF 0x7f7f7f7f7f7f7f7f
const bool debug = 0;

int n;
vector <int> num;
vector <pii> el;
vector <int> G[505050];
vector <int> dfs_tree;
bool vst[505050];
void coord_comp()
{
    sort(all(num));
    num.erase(unique(all(num)),num.end());
    for (auto &it:el)
    {
        it.first = lower_bound(all(num),it.first)-num.begin();
        it.second = lower_bound(all(num),it.second)-num.begin();
        G[it.first].push_back(it.second);
        G[it.second].push_back(it.first);
    }
}
void dfs(int r)
{
    dfs_tree.push_back(r);
    vst[r] = true;
    for (auto it:G[r])
        if (!vst[it])
            dfs(it);
}
int ans;
int32_t main()
{
    usecppio
    cin >> n;
    for (int i = 0; i<n; i++)
    {
        int a, b; cin >> a >> b;
        num.push_back(a); num.push_back(b);
        el.push_back({a, b});
    }
    coord_comp();
    int m = num.size();
    for (int i = 0; i<m; i++)
    {
        if (vst[i])
            continue;
        dfs(i);
        int edc = 0;
        for (auto it:dfs_tree)
            edc += G[it].size();
        edc /= 2;
        for (auto it:dfs_tree)
            ans += (num[it])*(G[it].size()-1);
        if (dfs_tree.size()>edc)
            ans += (num[*max_element(all(dfs_tree))]);
        dfs_tree.clear();
    }
    cout << ans << '\n';
}