[C/C++] 백준 #2243 사탕상자(세그먼트 트리)

#2243 문제는 백준 사이트에서 자주 나오는 고급 문제인 세그먼트 트리 문제입니다.

 

세그먼트 트리가 이미 많이 알려져서, 사실 이제는 그렇게 어려운 알고리즘이라고 할 수도 없습니다.

 

문제 링크입니다.

https://www.acmicpc.net/problem/2243

2243번: 사탕상자

세그먼트 트리는 쿼리의 종류가 두가지인 경우에 사용할 수 있습니다.  저는 읽는 쿼리와 쓰는 쿼리라고 이야기를 합니다.

 

 

읽는 쿼리만 있는 경우에는 전체의 개수가 N, 쿼리의 개수가 M인 경우,  \(O(M+N)\) 형태가 많습니다.  하지만 이렇게 만들어진 경우 쓰기 쿼리가 있으면, 쓸 때에는 N 시간을 소모하기 때문에 \(O(MN)\) 알고리즘이 됩니다.  세그먼트 트리는 그 둘의 타협점을 찾아서 \(O(M \log N)\)이 되도록 하는 것이 목표입니다.

 

세그먼트 트리를 이용해서 풀어본 다른 문제들입니다.

https://sdev.tistory.com/1106

[C/C++] 백준 #2042 구간 합 구하기(세그먼트 트리)

https://sdev.tistory.com/958

백준 #1849 순열(세그먼트 트리)

https://sdev.tistory.com/598

#1395 스위치(Segment Tree)

https://sdev.tistory.com/512

백준 #1275 커피숍2

 

세그먼트 트리 기법을 이용해서 풀 수 있는 문제들이 많으니, 세그먼트 트리는 백준을 하는데 있어서 꼭 알아두시면 좋습니다.  그리고 삼성소프트웨어 코딩 테스트에서도 세그먼트 트리는 간혹 출제된다고 합니다.

 

제가 작성한 소스입니다.  여기서는 클래스를 만들어서 해보았습니다.

//----------------------------------------------------------
//    baekjoon #2243 - Candy Box
//        - by Aubrey Choi
//        - created at 2020-01-22
//----------------------------------------------------------
#include <stdio.h>
#include <memory.h>
#define    END    1000000

//    Segment tree
class SegmentTree
{
public:
    SegmentTree(int n)
    {
        int s=1; while(s<n) s<<=1;
        tree = new int[s<<1];
        memset(tree,0,sizeof(int)*(s<<1));
    }
    ~SegmentTree() { delete[] tree; }
    int update(int c, int s, int e, int idx, int x)
    {
        if(idx<s||idx>=e) return tree[c];
        if(s+1==e) return tree[c]+=x;
        int m = (s+e)/2;
        return tree[c] = update(c*2,s,m,idx,x)+update(c*2+1,m,e,idx,x);
    }
    int find(int c, int s, int e, int x)
    {
        if(s+1==e) return s;
        int m = (s+e)/2;
        if(x<=tree[c*2]) return find(c*2,s,m,x);
        return find(c*2+1,m,e,x-tree[c*2]);
    }
private:
    int *tree;
};

int main()
{
    int n, s, a, b;
    SegmentTree tree(END);
    scanf("%d",&n);
    while(n--)
    {
        scanf("%d", &s);
        if(s==1)
        {
            scanf("%d",&a);
            b=tree.find(1,0,END,a);
            printf("%d\n",b+1);
            tree.update(1,0,END,b,-1);
        }
        else
        {
            scanf("%d%d",&a,&b);
            tree.update(1,0,END,a-1,b);
        }
    }
}