[BOJ_2243_RN] 사탕상자 Problem Solving

문제 출처 : https://www.acmicpc.net/problem/2243

문제 해결에 필요한 알고리즘 : 펜윅 트리 ( Fenwick Tree ), 이분 탐색

해설

사실 이 문제는 Red-Black Tree 나 Treap 같은 자료구조를 이용해 해결 할 수 있는 문제다. 하지만 펜윅 트리를 이용해서 간단하게 구현이 가능하다.

번호순대로 사탕을 가지고 있을 때 정렬된 사탕 기준으로 k ( k는 임의의 정수 )번째 사탕을 구하는 문제이다. 누적합 ( DP ) 를 이용해서 문제를 해결할 수 있지만, 업데이트속도가 매우 느리다. 그래서 이 부분을 펜윅트리로 대체해 빠르게 업데이트가 가능하다.

펜윅트리를 이용해 누적합을 가지고 있을 때 k번째 사탕을 구하기 위해 이분탐색을 사용하면 된다. lower bound 기법을 적용 해 간단하게 찾을 수 있다.

시간복잡도

펜윅트리를 이용한 코드의 시간복잡도는 업데이트, 검색이 이다. k번째 수를 구하는 이분탐색은 N번 진행하므고 탐색할때마다 검색을 하므로 업데이트를 총 번 진행한다. 그래서 최종 시간 복잡도는 이다.

Red-Black Tree나 Treap같은 자료구조를 사용하면 삽입 삭제 k번째 수 구하기가 으로 가능해 이 작업이 총 N번 일어나므로 이다. 하지만 구현이 복잡하므로 극한의 초기화가 필수이거나 사탕의 범위가 크다면 사용하는것을 추천한다.

사탕상자 코드 [ C ]

#include <stdio.h>
#define MAX 1000000
int pe[MAX + 1];
void update(int i, int diff) {
    for (; i <= MAX; i += i & -i) {
        pe[i] += diff;
    }
}
int find(int i) {
    int res = 0;
    for (; i; i -= i & -i) {
        res += pe[i];
    }
    return res;
}
int main() {
    int i, n;
    scanf("%d", &n);
    for (i = n; i--; ) {
        int a, b, c;
        scanf("%d", &a);
        if (a - 1) {
            scanf("%d%d", &b, &c);
            update(b, c);
            continue;
        }
        scanf("%d", &b);
        int l, r;
        l = 1;
        r = MAX;
        for (; l < r; ) {
            int mid = l + r >> 1;
            int cnd = find(mid);
            if (cnd >= b) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        update(l, -1);
        printf("%d\n", l);
    }
    return 0;
}