[C++ 백준 풀이] 13059번 : Tourists (LCA) / 10090번 : Counting Inversions (세그먼트 트리)

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

 

문제의 난이도는 Solved.ac 기준 Platinum IV에 해당하며, 문제를 풀이하기 위해 LCA(최소 공통 조상) 알고리즘에 대한 지식이 필요합니다.

 

 

13059번 : Tourists

 

문제가 영문이고 길이가 길지만, 주어진 그림과 예시를 읽어보면 쉽게 이해가 가능한 문제입니다.

y > x이고 y = ax인 모든 (x, y)에 대해 x에서 y로 갈 때 거치는 노드(양 끝 x, y 노드 포함)의 총 합을 구하는 문제입니다.

위의 경우에는 저렇게 55개의 노드를 거치므로 답으로 55를 출력해주면 됩니다.

 

 

#include <cstdio>
#include <vector>
#define MAX 200001
using namespace std;
 
int Parent[MAX][20], Dist[MAX][20] = {}, Depth[MAX], H = 0;
vector<int> Line[MAX];
 
void setParent(int Par, int Node, int Dep) {
    if(!Line[Node].size()) return;
    Parent[Node][0] = Par;
    Dist[Node][0] = 1;
    Depth[Node] = Dep;
    for(int i=0; i<Line[Node].size(); i++)
        if(Line[Node][i] != Par) setParent(Node, Line[Node][i], Dep+1);
}
 
int findLCADis(int A, int B) {
    int Dis = 0;
    if(Depth[A] != Depth[B]) {
        if(Depth[A] < Depth[B]) swap(A, B);
        int Diff = Depth[A] - Depth[B];
        for(int i=0; Diff>0; i++) {
            if(Diff%2) {
                Dis += Dist[A][i];
                A = Parent[A][i];
            }
            Diff >>= 1;
        }
    }
    if(A != B) {
        for(int i=H; i>=0; i--)
            if(Parent[A][i] != 0 && Parent[A][i] != Parent[B][i]) {
                Dis += (Dist[A][i] + Dist[B][i]);
                A = Parent[A][i];
                B = Parent[B][i];
            }
        Dis += (Dist[A][0] + Dist[B][0]);
        A = Parent[A][0];
    }
    return Dis;
}
 
int main() {
    int N, M, A, B, temp;
    long long Sum = 0;
    scanf("%d", &N);
    temp = N;
    while(temp > 1) {
        temp /= 2;
        H++;
    }
    for(int i=0; i<N-1; i++) {
        scanf("%d %d", &A, &B);
        Line[A].push_back(B);
        Line[B].push_back(A);
    }
    setParent(0, 1, 0);
    for(int i=1; i<=H; i++)
        for(int j=2; j<=N; j++)
            if(Parent[j][i-1]) {
                Parent[j][i] = Parent[Parent[j][i-1]][i-1];
                Dist[j][i] = Dist[j][i-1] + Dist[Parent[j][i-1]][i-1];
            }
    for(int i=1; i<=N; i++)
        for(int j=i*2; j<=N; j+=i)
            Sum += (long long)(findLCADis(i, j)+1);
    printf("%lld", Sum);
}
 

 

풀이는 위와 같으며, LCA 알고리즘을 기반으로 풀이하였습니다.

경로에서 노드 사이의 간선의 수를 구하고 거기에 1을 더해주면 결국 거쳐가는 노드의 수가 됩니다.

따라서 우선은 경로의 길이에 초점을 맞추어, 모든 dist를 1로 저장해주고, parent를 갱신하는 부분에서 dist 역시 2^k 상위에 있는 부모 노드의 거리를 갱신해주었습니다.

나머지는 적절히 for문을 작성하여, 모든 거리들의 합을 구해주기만 하면 됩니다.

 

 

 

코드를 제출해보면 1초 미만으로 돌아가긴 하지만, 애초에 문제에서 제한 시간을 5초로 넉넉하게 주었기 때문에 괜찮습니다. (쿼리의 수가 20억개까지 들어올 수 있기 때문)

그리고 문제 조건에서 N이 최대 20만개까지 들어올 수 있으므로, MAX 크기 역시 20만 이상으로 잡아주어야 합니다. (그렇지 않으면 bad alloc 컴파일 에러 발생)

 

 

10090번 : Counting Inversions

 

문제가 영문이지만 잘 해석해보면 Inversion Counting Problem임을 알 수 있습니다.

그렇지 않더라도 문제의 제목만 보고도 문제의 내용을 어느정도 유추 가능합니다.

 

[C++ 백준 풀이][Platinum V] 7578번 : 공장 (세그먼트 트리 응용, Inversion Counting Problem)

 

해당 알고리즘에 대한 자세한 설명은 위의 링크를 참고하시는 것을 추천드립니다.

 

 

#include <cstdio>
#include <vector>
using namespace std;
 
vector<int> Tree;
 
void updateTree(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(Node*2, Begin, Mid, Index);
    updateTree(Node*2+1, Mid+1, End, Index);
    Tree[Node] = Tree[Node*2] + Tree[Node*2+1];
}
 
int countLarge(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 countLarge(Node*2, Begin, Mid, Left, Right) + countLarge(Node*2+1, Mid+1, End, Left, Right);
}
 
int main() {
    int N, Value;
    long long Count = 0;
    scanf("%d", &N);
    Tree.resize(N*4);
    for(int i=0; i<N; i++) {
        scanf("%d", &Value);
        Count += (long long)countLarge(1, 1, N, Value+1, N);
        updateTree(1, 1, N, Value);
    }
    printf("%lld", Count);
}
 

 

풀이는 위와 같고, 전형적인 세그먼트 트리를 활용하는 문제입니다.

어떤 수의 뒤에 어떤 수보다 작은 수를 count 하는 것은, 그냥 순서대로 수를 입력받으면서 이전에 입력받았던 수들 중에 어떤 수보다 큰 수가 몇 개 있었는지를 count 한 것과 같습니다.

따라서 입력을 받는 즉시 countLarge 함수를 수행해서 값을 더해주고, tree에 update 해주는 과정을 반복해서 count의 총합을 구해주면 됩니다.

 

 

 

제출해보면 꽤 오랜 시간이 소요되며 테스트케이스들을 통과했음을 확인할 수 있습니다.