백준 2243번 [사탕상자](C++)-yes6686- 티스토리

백준 문제 풀이: 2243 [사탕상자]

---

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

문제 설명:

사탕 상자에 여러 가지 맛의 사탕이 있으며, 이 사탕들을 꺼내거나 추가할 수 있는 기능을 제공합니다. 사탕 상자는 총 1,000,000개의 칸으로 이루어져 있으며, 각 칸에 사탕이 들어 있습니다. 두 가지 작업을 수행합니다:

• 맛의 순서에 따라 사탕을 꺼내는 작업
• 특정 맛의 사탕을 추가하는 작업

---

문제 해결 코드

#include <iostream>
using namespace std;

int arr[1000001];
int tree[4000001];

int query(int n, int s, int e, int d) {
    if (s == e) return e;
    if (tree[2 * n] >= d) {
        return query(2 * n, s, (s + e) / 2, d);
    } else {
        return query(2 * n + 1, (s + e) / 2 + 1, e, d - tree[2 * n]);
    }
}

void update(int n, int s, int e, int i, int v) {
    if (i < s || e < i) return;
    if (s == e) {
        tree[n] = v;
        return;
    }
    update(2 * n, s, (s + e) / 2, i, v);
    update(2 * n + 1, (s + e) / 2 + 1, e, i, v);
    tree[n] = tree[2 * n] + tree[2 * n + 1];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;
    int a, b, c;

    for (int i = 0; i < n; i++) {
        cin >> a;
        if (a == 1) { // 꺼내기 작업
            cin >> b;
            int k = query(1, 0, 1000000, b);
            cout << k + 1 << '\n';
            arr[k] -= 1;
            update(1, 0, 1000000, k, arr[k]);
        } else if (a == 2) { // 추가 작업
            cin >> b >> c;
            arr[b - 1] += c;
            update(1, 0, 1000000, b - 1, arr[b - 1]);
        }
    }
    return 0;
}

---

코드 설명

• 핵심 알고리즘: 세그먼트 트리를 사용하여 사탕 상자의 상태를 관리합니다.
• 구현 세부사항:
  • query: 특정 순서의 사탕을 꺼낼 때, 해당 사탕의 위치를 세그먼트 트리에서 탐색합니다.
  • update: 특정 맛의 사탕 개수를 업데이트합니다.
  • 배열 arr: 각 맛의 사탕 개수를 저장하며, 이를 기반으로 세그먼트 트리를 갱신합니다.
• 시간 복잡도: O(log n)
  • 각 query와 update 연산은 세그먼트 트리를 탐색하므로 O(log n)

---

결과

입력된 작업에 따라 정확히 사탕을 꺼내거나 추가하며, 세그먼트 트리를 통해 효율적으로 수행됩니다. 이 코드는 대규모 입력에도 빠르게 동작합니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!