백준(BOJ) 2243 사탕상자 C++ 풀이

문제 링크: https://www.acmicpc.net/problem/2243

2243번: 사탕상자

문제 풀이에 이용된 알고리즘: 세그먼트 트리

 

사탕 상자 내에 k번째로 맛있는 사탕을 구하기 위해서, 어떤 식으로 세그먼트 트리를 만들지와 어떤 식으로 쿼리를 날릴지를 결정하면 쉽게 풀 수 있는 문제이다.(본인에게는 앞에 두세가지 조건이 많이 어려웠다.)

 

사탕의 맛은 1~1000000까지 연속적이다.

 

맛이 i인 사탕이 몇개인지를 arr[i]라고 하고, 세그먼트 트리를 구성하도록 한다.

 

세그먼트 트리의 한 노드의 구간 (a,b)는 맛이 a부터 b까지에 포함되는 사탕의 개수를 의미한다.

 

그렇다면 k번째로 맛있는 사탕은 어떻게 구할까?

 

세그먼트 트리에서 한 노드의 왼쪽 자식 노드 L과 오른쪽 자식 노드 R이 있다고 상상하자.

 

일단 L에 포함되는 사탕들이, R에 포함되는 사탕들보다는 맛있는 사탕들임을 이해할 수 있는가?(중요하지는 않지만, 현재 세그먼트 트리의 구성을 파악하는지 확인하기 위한 좋은 질문이다.)

 

1. 이 때, L노드의 값이 k보다 크다면, L노드가 의미하는 구간에 k번째 사탕이 존재한다는 것을 의미한다.

왜냐! 결국 k번째로 맛있는 사탕을 찾는 것인데 L 노드의 값이 k보다 크다는 것은, L을 구성하는 사탕들 사이에 k번째로 맛있는 사탕이 존재한다는 의미이기 때문이다.

(L노드의 "값"과 "의미하는 구간"이라는 용어를 사용하고 있는데, 그 차이와 의미를 명확하게 이해하자)

 

2. L노드의 값이 k보다 작다면, L이 아닌 R에서 k번째로 맛있는 사탕을 찾아야한다.

단, L노드의 값을 tree[L]이라고 했을 때, R에서 찾아야 하는 것은 k번째로 맛있는 사탕이 아니라, (k-tree[L])번째로 맛있는 사탕을 찾는 것임을 명심하자.

 

나(R)보다 앞쪽 구간에서 나보다 맛있는 사탕이 tree[L]개 만큼있으면, 내 구간에서는 그 숫자만큼을 제외해야하는 것이 자명하다.

 

그리고, 사탕을 꺼내거나 넣을 때마다 지속적인 사탕 개수 업데이트가 필요하다.

 

/* BOJ 2243 사탕 상자 */
#define _CRT_SECURE_NO_WARNINGS
 
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include <cstring>
#include <string>
#include <string.h>
 
#define endl '\n'
 
using namespace std;
 
typedef long long ll;
 
const int MAX = 1000001;
int n;
ll arr[MAX];
ll tree[MAX * 4];
 
ll query(int node, int start, int end, int k) // 상자 안에서 k번째로 맛있는 사탕 찾기
{
    if (start == end) return end;
 
    int mid = (start + end) / 2;
    if (tree[node * 2] >= k)
        return query(node * 2, start, mid, k);
    else
        return query(node * 2 + 1, mid + 1, end, k - tree[node * 2]);
}
 
void update(int node, int start, int end, int idx, ll value) // 상자 속 사탕 현황 갱신
{
    if (idx < start || idx > end) return;
    if (start == end)
    {
        tree[node] = value;
        return;
    }
 
    int mid = (start + end) / 2;
    update(node * 2, start, mid, idx, value);
    update(node * 2 + 1, mid + 1, end, idx, value);
    tree[node] = tree[node * 2] + tree[node * 2 + 1];
}
 
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    freopen("input.txt", "r", stdin);
 
    cin >> n;
 
    ll a, b, c;
    for (int i = 0; i < n; i++)
    {
        cin >> a;
        if (a == 1) // 사탕 꺼내기
        {
            cin >> b;
            // b번째 사탕을 꺼냈을 때, 해당 사탕의 맛을 k라고함
            int k = query(1, 1, MAX, b);
            cout << k << endl;
            // 하나 꺼냈으니 세그트리 업데이트
            update(1, 1, MAX, k, arr[k] - 1);
            arr[k]--;
        }
        else // 사탕 넣거나 버리기
        {
            cin >> b >> c;
            // b라는 맛의 사탕을
            update(1, 1, MAX, b, arr[b] + c);
            arr[b] += c; // c개 넣기 또는 빼기
        }
    }
 
    return 0;
}