백준 3653번 영화 수집

문제 링크입니다: https://www.acmicpc.net/problem/3653

난이도가 높은 세그먼트 트리 응용 문제였습니다.

많은 사람들이 펜윅 트리로 풀었지만 세그먼트 트리 알고리즘으로는 풀리지만 펜윅 트리 알고리즘으로는 풀리지 않는 문제들이 존재하기 때문에 세그먼트 트리 알고리즘을 이용하여 풀었습니다.

알고리즘과 코드는 lyzqm(https://lyzqm.blogspot.com/2017/07/segment-tree-3653.html?showComment=1531981580261#c7391195554365601508)님의 블로그를 참고하여 풀었습니다.

기본적인 알고리즘은 아래와 같습니다.

1. 배열을 M + N 크기로 설정하고 (M ~ N - 1)까지 1로 표시하고 (0 ~ M - 1)까지는 0으로 표시합니다. 즉, (0 ~ M - 1)은 현재 빈 공간이고 M 부터 1번 DVD의 위치를 표시한 것입니다.(자세한 그림은 lyzqm 블로그에 포스팅 되어있습니다.)

2. 현재 배열이 (0 ~ M - 1)까지는 빈 공간이고 M번부터 DVD의 위치가 차례대로 배치되어있기 때문에 DVD 번호가 주어졌을 때 (0 ~ 배열[해당 DVD 번호] - 1)까지의 구간 합을 구해줍니다. 

3. 확인한 DVD를 맨 위로 배치하는 과정을 현재 빈 공간 중 끝인  M - 1번 인덱스에 배치하는 방식으로 진행합니다.(물론 기존에 DVD가 배치되어 있던 곳은 비워지고 현재 DVD가 배치되어 있던 곳은 채워진다.) 이렇게 되면 (0 ~ 배열[해당 DVD 번호] - 1)까지의 구간 합은 0이 되므로 맨 위에 배치된 것으로 판단해도 됩니다.

4, 2 ~ 3번 과정을 반복하는데 3번의 빈 공간은 한 칸씩 줄어들므로 M - 1 -> M - 2 -> M -3 -> ... 이런식으로 업데이트 해줘야합니다.

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

 

struct segmentTree

{

        int size;

        vector<long long> tree, collection;

        segmentTree(int N, int M)

        {

                 size = N + M;

                 collection.resize(N);

                 tree.resize(4 * size, 0);

        }

        //세그먼트 트리 초기화

        long long init(int node, int M, int start, int end)

        {

                 if (start == end)

                 {

                         if (start >= M)

                         {

                                 collection[start - M] = start;

                                 tree[node] = 1;

                         }

                         return tree[node];

                 }

 

                 int mid = (start + end) / 2;

                 return tree[node] = init(node * 2, M, start, mid) + init(node * 2 + 1, M, mid + 1, end);

        }

        void init(int M)

        {

                 init(1, M, 0, size - 1);

        }

        //구간 합 구하기

        long long query(int node, int start, int end, int nodeLeft, int nodeRight)

        {

                 if (end < nodeLeft || nodeRight < start)

                         return 0;

                 if (start <= nodeLeft && nodeRight <= end)

                         return tree[node];

 

                 int mid = (nodeLeft + nodeRight) / 2;

                 return query(node * 2, start, end, nodeLeft, mid) + query(node * 2 + 1, start, end, mid + 1, nodeRight);

        }

        long long query(int start, int end)

        {

                 return query(1, start, collection[end] - 1, 0, size - 1);

        }

        //세그먼트 트리 업데이트

        long long update(int idx, int node, int val, int nodeLeft, int nodeRight)

        {

                 if (idx < nodeLeft || nodeRight < idx)

                         return tree[node];

                 if (nodeLeft == nodeRight)

                         return tree[node] = val;

 

                 int mid = (nodeLeft + nodeRight) / 2;

                 return tree[node] = update(idx, node * 2, val, nodeLeft, mid) + update(idx, node * 2 + 1, val, mid + 1, nodeRight);

        }

        long long update(int idx, int val)

        {

                 return update(collection[idx], 1, val, 0, size - 1);

        }

        //해당 책 인덱스 업데이트

        void change(int idx, int val)

        {

                 collection[idx] = val;

        }

};

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0); //cin 속도 향상

        int test_case;

        cin >> test_case;

 

        for (int i = 0; i < test_case; i++)

        {

                 int N, M;

                 cin >> N >> M;

 

                 segmentTree segTree(N, M);

                 segTree.init(M);

 

                 //idx은 빈 공간 인덱스 표시

                 int idx = M - 1;

                 for (int j = 0; j < M; j++)

                 {

                         int num;

                         cin >> num;

 

                         cout << segTree.query(0, num - 1) << " ";

                         segTree.update(num - 1, 0); //해당 디비디를 꺼내고

                         segTree.change(num - 1, idx); //디비디의 위치를 바꾼다

                         segTree.update(num - 1, 1); //누적합 업데이트

                         idx--; //빈 공간

                 }

                 cout << "\n";

        }

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~

참고: [프로그래밍 대회에서 배우는 알고리즘 문제해결전략]