[백준] 2243: 사탕상자

0. 문제 주소

 

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

2243번: 사탕상자

 

 

1. 풀이

 

세그트리를 이용해서 맛의 좋고 나쁨을 나타내는 1부터 100만까지의 수에 대해서, 구간 합을 저장하는 세그트리를 만든다.

 

맨 처음 사탕의 개수는 모두 0이므로 초기 construct 함수도 필요 없고, 답을 찾는 find 함수 특성상 get_sum 함수도 필요 없다.

 

필요한 함수는 기존과 동일한 update 함수와, 아래와 같은 find 함수이다.

 

int find(int node, int s, int e, int remain){
    if (s==e) return s;
    
    int mid = (s+e)/2;
    int left_child = tree[node*2];
    if (remain > left_child){
        return find(node*2+1, mid+1, e, remain - left_child);
    }
    else{
        return find(node*2, s, mid, remain);
    }
}

 

"특정 순서에 있는 원소"를 찾는다는 점에서 [PS/DP] - [BOJ] 1256: 사전과 비슷하다.

 

루트 노드(1번)부터 탐색을 시작해서, remain 값과 왼쪽 자식에 저장되어 있는 값을 비교한다.

 

remain 값은 남아있는 순서의 개수라고 생각하면 된다.

맨 처음 find 함수를 호출할 땐 구해고자 하는 순위를 넣어주는데, 아래 예시를 보자.

 

 

 

1번 노드에 0번 원소부터 15번 원소까지의 합인 12가 저장되어있고, 그 왼쪽 자식에 7, 오른쪽 자식에 5가 저장되어 있다.

 

찾고 싶은 순위를 8이라고 해보자.

 

찾으려하는 값이 왼쪽 자식에 저장되어 있는 7보다 크다.

 

이는 0번 원소에서 7번 원소 중에는 우리가 원하는 답이 없다는 뜻과 같다. 

 

이 경우 재귀적으로 노드 번호엔 오른쪽 자식의 노드 번호를, remain 값에는 (기존 remain값 - 왼쪽 자식의 값)을 대입해주어

 

결론적으로 탐색하는 범위의 처음과 끝이 같아질 때 까지 ( s = e ) 탐색을 반복한다.

 

 

2. 풀이 코드

 

* 유의할 점

 

 

#include <iostream>
#include <cmath>

#define MAX 1000000

using namespace std;

int N;
int tree[1<<21];
int leaf_size;

void update(int i, int diff){
    i += leaf_size;
    tree[i] += diff;
    while(i>1){
        i/=2;
        tree[i] = tree[i*2] + tree[i*2+1];
    }
}

int find(int node, int s, int e, int remain){
    if (s==e) return s;
    
    int mid = (s+e)/2;
    int left_child = tree[node*2];
    if (remain > left_child){
        return find(node*2+1, mid+1, e, remain - left_child);
    }
    else{
        return find(node*2, s, mid, remain);
    }
    
}

int main(){
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    #endif
    
    leaf_size = 1 << (int)(ceil(log2(MAX)));
    
    scanf("%d", &N);
    int op, b, c, pos;
    for (int i=0;i<N;i++){
        scanf("%d", &op);
        if (op == 1){
            scanf("%d", &b);
            pos =  find(1, 0, leaf_size-1, b);
            printf("%d\n", pos+1);
            update(pos, -1);
        }
        else {
            scanf("%d %d", &b, &c);
            update(b-1, c);
        }
    }
    
    
    return 0;
}