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

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

 

문제의 난이도는 Solved.ac 기준 Platinum V에 해당하며, 세그먼트 트리의 응용 개념과 Inversion Counting Problem에 대해 짚고 넘어갈 것입니다.

 

Inversion Counting Problem이란 말 그대로 두 쌍의 데이터들 중에서 역순으로 배열되어 있는 쌍들의 수를 찾는 문제입니다.

 

이전에 해결했던 1517번 : '버블 소트' 문제 역시 Inversion Counting Problem의 관점에서 해결할 수 있습니다.

 

[C++ 백준 풀이][Platinum V] 1517번 : 버블 소트 (세그먼트 트리 응용)

↑ 풀이는 위의 링크에 정리되어 있으니, 참고하실 수 있습니다.

 

그럼 이제 이 포스트에서 다룰 공장 문제를 풀이해보도록 하겠습니다.

 

 

7578번 : 공장

 

N개의 기계가 두 쌍으로 존재할 때, 두 줄에서 각각 순서대로 기계들의 번호를 입력받아 같은 번호의 기계들을 연결할 때, 연결선의 교차가 몇 번 발생하는지를 구하는 문제입니다.

어느 한 쪽의 데이터가 정렬되었다면, 위에 링크를 첨부한 '버블 소트' 문제와 같이 해결하면 되겠지만, 이 문제에서는 양 쪽의 데이터가 모두 정렬되어있지 않습니다.

따라서 그냥 순차적으로 윗줄의 특정 번호를 가진 로봇이 아랫줄에는 몇 번째에 있는지를 구해서 트리에 하나씩 대입해보면서 그 갯수를 Count하는 식으로 풀이해야 합니다.

 

 

↓ 위의 이미지와 동일한 풀이 코드는 아래의 접은 글에 정리되어 있습니다.

#include <cstdio>
#include <vector>
#define MAX 1000000
using namespace std;

vector<int> A, B;
vector<long long> Tree;

void updateTree(int Node, int Begin, int End, int Index) {
    if(Index < Begin || Index > End) return;
    Tree[Node]++;
    if(Begin < End) {
        int Mid = (Begin + End)/2;
        updateTree(Node*2, Begin, Mid, Index);
        updateTree(Node*2+1, Mid+1, End, Index);
    }
}

long long calcSum(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 calcSum(Node*2, Begin, Mid, Left, Right) + calcSum(Node*2+1, Mid+1, End, Left, Right);
}

int main() {
    int N, Value;
    long long Ans = 0;
    scanf("%d", &N);
    A.resize(N+1), B.resize(MAX+1), Tree.resize(N*4+1);
    for(int i=1; i<=N; i++) scanf("%d", &A[i]);
    for(int i=1; i<=N; i++) {
        scanf("%d", &Value);
        B[Value] = i;
    }
    for(int i=1; i<=N; i++) {
        Ans += calcSum(1, 1, N, B[A[i]]+1, N);
        updateTree(1, 1, N, B[A[i]]);
    }
    printf("%lld", Ans);
}

 

먼저 메인 함수에 구현된 scanf 부분의 원리는 다음과 같습니다.

A 라인 스캔 : i번째 Val을 A[i]에 저장
B 라인 스캔 : i를 B[Val]에 저장

그러면 A[i]를 가지고 B에 대입하여, B[A[i]] = B[Val] = i를 찾을 수 있게 됩니다.

즉 A의 i번째 로봇이 B의 몇 번째에 있는지 알 수 있습니다.

ex ) B[A[2]] = 4  : A줄의 2번째 위치의 번호를 가진 로봇이 B줄에서는 4번째에 있음

 

** 여기서 B는 Index로써 Value 값을 대입받기 때문에, resize를 선언할 때 그 크기를 기계 번호의 범위에 해당하는 100만이상으로 잡아야 합니다. (그보다 작게 잡으면 당연히 그 밖의 주소를 참조하게 되어 컴파일 에러가 발생하게 됨)

 

이제 A의 i번째 로봇의 위치를 알았으면, B줄에서 오른쪽에 있으나 A줄에서는 더 왼쪽에 있는 로봇들의 수를 calcSum 함수에서 세어줍니다. (지금 보니까 함수의 이름을 findCnt로 이름을 붙이는 것이 더 적절했을 것 같습니다.)

윗 줄에서는 더 왼쪽에 있고 아랫 줄에서는 더 오른쪽에 있는 로봇과는 그 연결선이 교차가 되기 때문입니다.

 

그렇다면 이 Count 값을 계산하는 트리는 어떻게 설계되었는지 updateTree 함수를 봅시다.

updateTree 함수에서는 단순히 Index를 포함하고 있는 노드를 따라 내려가면서 그 값을 1씩 증가시켜 주었습니다.

이렇게 트리를 구현한다면 calcSum 함수에서 B[A[i]]보다 오른쪽에 있는 노드들의 구간합을 구해오기만 하면, B줄에서 앞서 입력받은 로봇들과 발생하는 교차점의 수를 쉽게 구할 수 있게 됩니다.

 

모든 로봇에 대해 같은 연산을 수행하면, B줄의 2번째 로봇은 1번째 로봇과 교차가 발생하는지 계산하고, 3번째 로봇은 1~2번째 로봇과 몇 번 교차가 발생하는지 계산하고, 4번째 로봇은 1~3번째 로봇과, ... , N번째 로봇은 1~N-1번째 로봇과 몇 번의 교차가 발생하는지 계산을 하게 되어 총 교차 선의 수를 계산할 수 있게 됩니다.

 

이렇게 계산한 Ans 값을 출력해주기만 하면 풀이 코드를 완성할 수 있습니다.

 

 

 

풀이를 제출해보면 위와 같이 432ms 시간이 소요되고 정답 처리를 받을 수 있습니다.

Inversion Counting Problem을 세그먼트 트리를 활용해서 풀이하는 것이 인상깊었습니다.