[C++ 백준 풀이] 13372번 : Glass Bridge / 13681번 : Bolhas e Baldes / 5847번 : Milk Scheduling

이 포스트에서는 프로그래밍 문제 사이트 백준 Online Judge의 13372번 : 'Glass Bridge' 문제에 대한 풀이 코드와 해설을 다루고 있습니다.

 

문제의 난이도는 Solved.ac 기준 Platinum V에 해당하며, 풀이를 위해 세그먼트 트리에 대한 기본 이해가 필요합니다.

 

 

13372번 : Glass Bridge

 

영어를 간단히만 할 수 있으면 해석할 수 있는 문제입니다.

그림만 봐도 대충 감이 올텐데, 위와 같이 1~N번 사이의 번호를 반대편의 주어진 번호 순서대로 연결했을 때 발생하는 교차점의 개수를 구하는 문제입니다.

당연히 N이 10만 이하이므로 O(N^2) 알고리즘으로는 해결할 수 없는 문제입니다.

 

 

#include <cstdio>
#include <vector>
using namespace std;
 
void updateTree(vector<long long> &Tree, int Node, int Begin, int End, int Index) {
    if(Index < Begin || Index > End) return;
    if(Begin == End) {
        Tree[Node] = 1;
        return;
    }
    int Mid = (Begin + End)/2;
    updateTree(Tree, Node*2, Begin, Mid, Index);
    updateTree(Tree, Node*2+1, Mid+1, End, Index);
    Tree[Node] = Tree[Node*2] + Tree[Node*2+1];
}
 
long long cntBigger(vector<long long> &Tree, int Node, int Begin, int End, int Left, int Right) {
    if(Left > End || Right < Begin) return 0;
    if(Left <= Begin && Right >= End) return Tree[Node];
    int Mid = (Begin + End)/2;
    return cntBigger(Tree, Node*2, Begin, Mid, Left, Right) + cntBigger(Tree, Node*2+1, Mid+1, End, Left, Right);
}
 
int main() {
    int T, N, Value;
    scanf("%d", &T);
    for(int i=0; i<T; i++) {
        long long Sum = 0;
        vector<long long> Tree;
        scanf("%d", &N);
        Tree.resize((N+1)*4);
        for(int i=1; i<=N; i++) {
            scanf("%d", &Value);
            Sum += cntBigger(Tree, 1, 1, N, Value+1, N);
            updateTree(Tree, 1, 1, N, Value);
        }
        printf("%lld\n", Sum);
    }
}
 

 

숫자들의 나열을 잘 생각해보면 쉽게 원리를 떠올릴 수 있습니다.

먼저 1에 대응되는 첫 번째 숫자인 4를 먼저 놓고, 그 다음 두 번째 숫자인 8을 놓고 보면 4보다 작은 수였을 경우 교차가 발생하였는데 4보다 큰 8이기 때문에 교차가 발생하지 않습니다.

이런 원리로 생각해보면 3번째 숫자인 1은, 4보다도 작고 8보다도 작으므로 2번의 교차가 발생합니다.

이렇게 1번째 수부터 트리에 대입하면서 i번째 수 A[i]보다 큰 A[1] ~ A[i-1]이 몇 개 있는지 세어주면 됩니다.

이것을 위와 같이 세그먼트 트리로 구현할 수 있습니다.

 

 

 

또한 위의 문제는 Inversion Counting Problem으로도 알려져 있으니 참고하면 좋을 것 같습니다.

 

 

13681번 : Bolhas e Baldes

 

Marcelo와 Carlos가 게임을 하는데, 번호가 세워진 병들을 나열하는 게임입니다.

번호는 무작위로 놓여있으며 입력으로 주어지고, 인접한 두 병의 위치를 바꿀 수 있습니다.

이 때 순서가 정렬되어 있는 (3과 4와 같은) 병들은 움직일 수 없습니다. (4와 3은 가능)

그래서 Marcelo부터 수행을 시작하고 마지막에 움직일 수 없는 사람이 진다고 할 때, 주어진 입력에 대해 이기는 사람을 맞추는 게임입니다.

 

 

#include <cstdio>
#include <vector>
using namespace std;
 
void updateTree(vector<long long> &Tree, int Node, int Begin, int End, int Index) {
    if(Index < Begin || Index > End) return;
    if(Begin == End) {
        Tree[Node] = 1;
        return;
    }
    int Mid = (Begin + End)/2;
    updateTree(Tree, Node*2, Begin, Mid, Index);
    updateTree(Tree, Node*2+1, Mid+1, End, Index);
    Tree[Node] = Tree[Node*2] + Tree[Node*2+1];
}
 
long long cntBigger(vector<long long> &Tree, int Node, int Begin, int End, int Left, int Right) {
    if(Left > End || Right < Begin) return 0;
    if(Left <= Begin && Right >= End) return Tree[Node];
    int Mid = (Begin + End)/2;
    return cntBigger(Tree, Node*2, Begin, Mid, Left, Right) + cntBigger(Tree, Node*2+1, Mid+1, End, Left, Right);
}
 
int main() {
    int N, Value;
    while(1) {
        long long Sum = 0;
        vector<long long> Tree;
        scanf("%d", &N);
        if(!N) break;
        Tree.resize((N+1)*4);
        for(int i=1; i<=N; i++) {
            scanf("%d", &Value);
            Sum += cntBigger(Tree, 1, 1, N, Value+1, N);
            updateTree(Tree, 1, 1, N, Value);
        }
        if(Sum%2) printf("Marcelo\n");
        else printf("Carlos\n");
    }
}
 

 

막상 문제를 풀어보면 놀랍도록 위의 문제와 같은데, 이것은 문제 자체가 버블 정렬의 swap 횟수를 묻고 있기 때문입니다.

따라서 어떤 수를 기준으로 그 수보다 뒤에 더 작은 수가 몇 개나 있는지가 정렬의 기준이 되므로, 이것은 결국 정렬된 데이터와 주어진 데이터를 같은 번호끼리 연결했을 때 발생하는 교차점의 수를 묻는 것과 같습니다.

 

 

 

제출해보면 역시 정답을 인정받을 수 있습니다.

 

 

5847번 : Milk Scheduling

 

문제를 해석해보면 각 소마다 milking 하는데 걸리는 시간이 다르고 이들이 T[i]로 주어지며, 특정 소들에게는 반드시 어떤 다른 소보다 먼저 milking 해야 하는 순서가 있다고 할 때 이들을 모두 milking 하는데 걸리는 최소 시간을 구하는 문제입니다.

선후 연결관계가 없으면 다른 소들과 동시에 milking을 진행할 수 있으므로, 결국 연결 시간이 가장 긴 부분을 찾아 그 시간을 구하면 됩니다.

이것은 결국 시간을 간선으로, 소들을 노드로 생각했을 때 가장 긴 그래프를 찾는 위상정렬 문제로 변형시켜서 생각할 수 있습니다.

 

 

#include <cstdio>
#include <vector>
#include <queue>
#define MAX 10005
using namespace std;
 
int Degree[MAX], Time[MAX];
long long Sum[MAX];
vector<int> Node[MAX];
queue<int> Queue;
 
int main() {
    int N, M, X, Y, Pop, Next;
    long long Max = 0;
    scanf("%d %d", &N, &M);
    for(int i=1; i<=N; i++) scanf("%d", &Time[i]);
    for(int i=1; i<=M; i++) {
        scanf("%d %d", &X, &Y);
        Node[X].push_back(Y);
        Degree[Y]++;
    }
    for(int i=1; i<=N; i++)
        if(!Degree[i]) {
            Queue.push(i);
            Sum[i] = Time[i];
        }
    while(!Queue.empty()) {
        Pop = Queue.front();
        Queue.pop();
        for(int i=0; i<Node[Pop].size(); i++) {
            Next = Node[Pop][i];
            if(Sum[Pop]+(long long)Time[Next] > Sum[Next])
                Sum[Next] = Sum[Pop] + (long long)Time[Next];
            Degree[Next]--;
            if(!Degree[Next]) Queue.push(Next);
        }
    }
    for(int i=1; i<=N; i++) if(Sum[i] > Max) Max = Sum[i];
    printf("%lld", Max);
}
 

 

Degree는 선행 노드들에 의해 연결되어 있는 간선의 수를 저장하고, Time은 각 milking에 소요되는 시간, 그리고 Node[x] = y는 x에서 y로 노드가 연결되어 있음을 의미합니다.

변수 선언만 위와 같이 해주면 나머지는 쉽게 해결이 되는데, 큐에다가 선행 노드가 없는 것들부터 처리하면서 각 노드를 기준으로 시간을 Sum에 저장하여 그들 중 가장 큰 Sum을 답으로 출력해주면 됩니다.

 

 

 

제출해보면 16ms 시간에 정답을 인정받을 수 있습니다.