[C++ 백준 풀이] 3653번 : 영화 수집 / 6213번, 6218번 : Balanced Lineup

이 포스트에서는 프로그래밍 문제 사이트 백준 Online Judge의 3653번 : '영화 수집'과 6213번, 6218번 : 'Balanced Lineup' 문제에 대한 풀이 코드와 해설을 다루고 있습니다.

 

문제의 난이도는 Solved.ac 기준 Gold I ~ Platinum IV에 해당하며, 문제를 풀이하기 위해 세그먼트 트리 응용 개념을 다룰 것입니다.

 

 

3653번 : 영화 수집

 

위에서부터 1번, 맨 아래를 N번 DVD라고 할 때 중간에 있는 DVD를 선택해서 맨 위에 올리는 과정을 M번 반복할 때, 선택한 시점에서 그 위에 쌓여있는 DVD의 수를 출력하는 문제입니다.

세그먼트 트리를 이용한다는 힌트를 이용해보면, 매 번 DVD를 선택할 때마다 맨 위부터 선택한 DVD 바로 위까지의 구간 합을 구해주면 되는 문제임을 알 수 있습니다.

 

 

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

#include <cstdio>
#include <vector>
#include <cmath>
using namespace std;

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

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

int main() {
    int T, N, M, DVDNum;
    scanf("%d", &T);
    for(int i=0; i<T; i++) {
        vector<int> Tree, Pos;
        scanf("%d %d", &N, &M);
        Tree.resize((N+M)*4+1), Pos.resize(N+1);
        for(int j=1; j<=N; j++) {
            Pos[j] = M+j;
            updateTree(Tree, 1, 1, M+N, Pos[j], 1);
        }
        for(int j=1; j<=M; j++) {
            scanf("%d", &DVDNum);
            printf("%d ", calcSum(Tree, 1, 1, M+N, 1, Pos[DVDNum]-1));
            updateTree(Tree, 1, 1, M+N, Pos[DVDNum], -1);
            updateTree(Tree, 1, 1, M+N, M+1-j, 1);
            Pos[DVDNum] = M+1-j;
        }
        printf("\n");
    }
}

 

우선 그냥 N개의 리프 노드가 있는 세그먼트 트리는 구현하기 쉽지만, 그렇게 구현해서는 풀 수가 없음을 알 수 있습니다.

그러나 문제에서 주어지는 쿼리의 수가 M개로 고정되어 있다는 사실을 이용하여, 왼쪽에 M개의 빈 리프 노드를 더 만들어 줍니다.

그 다음에 명령을 수행할 때마다 M+1~M+N번째 노드의 수를 제거하고 M번째부터 왼쪽으로 쌓아가면 됩니다.

그렇게 처리를 한다면 처리를 할 때마다 1번 리프 노드 ~ DVD를 선택한 위치-1 구간의 구간합을 구해서 답을 얻을 수 있게 됩니다.

 

문제는 DVD를 위로 옮기고 나서 또 다시 그 DVD를 선택할 수도 있기 때문에, 결국 DVD의 위치를 저장하는 배열을 하나 선언하기는 해야 합니다.

그래서 Pos라는 벡터를 선언하여 초기에는 i번째 DVD의 위치를 M+i번째로 초기화시켜주고, 이동할 때마다 마지막으로 DVD가 이동한 위치를 저장하였습니다.

 

나머지 부분은 그렇게 어렵지 않습니다.

M개의 명령이 수행되므로 왼쪽에 M개 이상의 리프 노드를 만들어서 구현한다는 점과, DVD의 마지막 이동 위치를 저장하는 벡터를 추가로 사용한다는 점만 주의하면 나머지는 일반적인 세그먼트 트리의 구현과 다른 점이 없습니다.

 

 

위의 코드를 제출해보면 316ms의 시간이 소요되고 모든 테스트케이스를 통과함을 확인할 수 있습니다.

문제의 난이도가 Platinum IV였던 것으로 기억하는데, 일반적인 세그먼트 트리에 아이디어를 추가로 활용해야 한다는 점이 인상깊었습니다.

 

 

6213번, 6218번 : Balanced Lineup

 

이 문제는 쉬운 세그먼트 트리 활용 문제이길래 그냥 가져와봤습니다.

푼 사람이 많이 없기는 한데 영어 문제라서 그런 것 같습니다.

문제를 요약하면 N개의 소가 주어지고 각각 그들의 키가 1~100만 사이로 주어질 때, Q개의 쿼리에 대해서 특정 구간에서 가장 큰 소와 가장 작은 소의 크기 차이를 출력하는 문제입니다.

 

 

 

 

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

#include <cstdio>
#include <vector>
#include <algorithm>
#define INF 1000001
using namespace std;

vector<int> Min, Max;

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

int findMin(int Node, int Begin, int End, int Left, int Right) {
    if(Left > End || Right < Begin) return INF;
    if(Left <= Begin && Right >= End) return Min[Node];
    int Mid = (Begin + End)/2;
    return min(findMin(Node*2, Begin, Mid, Left, Right), findMin(Node*2+1, Mid+1, End, Left, Right));
}

int findMax(int Node, int Begin, int End, int Left, int Right) {
    if(Left > End || Right < Begin) return 0;
    if(Left <= Begin && Right >= End) return Max[Node];
    int Mid = (Begin + End)/2;
    return max(findMax(Node*2, Begin, Mid, Left, Right), findMax(Node*2+1, Mid+1, End, Left, Right));
}

int main() {
    int N, Q, H, Left, Right;
    scanf("%d %d", &N, &Q);
    Min.resize(N*4+1), Max.resize(N*4+1);
    for(int i=1; i<=N; i++) {
        scanf("%d", &H);
        updateTree(1, 1, N, i, H);
    }
    for(int i=0; i<Q; i++) {
        scanf("%d %d", &Left, &Right);
        printf("%d\n", findMax(1, 1, N, Left, Right)-findMin(1, 1, N, Left, Right));
    }
}

 

풀이를 보면 코드가 길지만, 이것은 Min 전용 Tree와 Max 전용 Tree 그리고 함수들을 따로 만들었기 때문에 코드가 길어 보이는 것이지, 실질적인 내용은 중복되어 있어서 많지 않습니다.

소의 크기가 하나씩 입력될 때마다 updateTree에서 최댓값과 최솟값을 동시에 트리에 저장해주는 과정을 거쳤습니다.

키 차이를 출력할 때는 구간을 입력받아 left와 right 변수로 활용하고, findMax 함수에서 반환받은 값에서 findMin에서 반환받은 값을 빼서 출력해주면 됩니다.

 

 

범위 자체도 int형을 벗어나지 않도록 주어진 문제이기 때문에 오버플로우를 염려할 필요도 없습니다.

코드를 제출해보면 위와 같이 쉽게 해결됨을 확인할 수 있습니다.