백준, BOJ, 2243번, 사탕상자 : C++ [CPP]

indexed tree로 풀었다.

하지만 어떤 이유로 indexed tree로 풀었느냐..?

Indexed tree는 해당 숫자가 많은데 update가 자주될 때.. 사용하는 것 같다.

난 그랬다.

 

 

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

 

---

 

#맞은 풀이

#include <iostream>

using namespace std;


int idx_tree[1 << 21]; //2^21 크기. -> 단말 노드에 100만개를 넣어야하기 때문.
int n;
int base;// 단말 노드의 처음 idx값

//p번째 맛의 캔디의 개수를 v만큼 바꾸는 것.
void update(int p, long long v)
{
    p += (base - 1); //base - 1을 하는 이유는 B가 1부터 시작하기 때문(0번째 idx를 제외하고 숫자시작)
    idx_tree[p] += v;

    //단말노드를 바꿨으니
    //해당 idx_tree의 parent 업데이트(p가 0이 될 때까지)
    while (p >>= 1) //2로 나누면, 즉, rshift 1만큼 하면 parent idx가 나옴.
    {
        //해당 node(p)는 왼쪽 자식 노드 (2*p) + 오른쪽 자식 노드 (2*p +1)임.
        idx_tree[p] = (idx_tree[p << 1] + idx_tree[(p << 1) | 1]); //OR연산으로 덧셈연산
    }
}



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

    cin >> n;

    for (base = 1; base < 1000000; base <<= 1); //base 값이 몇인지 계산하는 과정.(shift 연산)
    //1000000이라면 base는 그보다 바로 큰 값인 2의 거듭제곱 수가 된다.


    //n번 작업
    for (int i = 0; i < n; i++) {
        int A, B, C;
        cin >> A >> B;

        //사탕 관리
        if (A == 2) {
            cin >> C;
            //사탕 빼기(B맛 사탕을 C개 빼거나 넣는다)
            update(B, C);
            continue;
        }



        //B번째 사탕 빼기
        int node = 1;
        while (node < base) {

            int lNode = node << 1; //왼쪽 자식 (왼쪽 구간에 몇 개 들어있나) -> 2배
            int rNode = (node << 1 | 1); //오른쪽 자식(오른쪽 구간에 몇 개 들어있나)-> 2배 + 1

            //우선 왼쪽노드로 설정한다.
            node = lNode;
            //만약 해당 노드에서 B번째를 찾을 수 없다면.
            if(B>idx_tree[node]){
                node += 1; //오른쪽 자식으로감.

                //오른쪽 노드로 간다면 해당 번째를 바꿔야함
                B -= idx_tree[lNode];

                //ex 2(lNode), 3(rNode)으로 나뉘는데 3번째를 찾으려면 오른쪽 노드로 가야하고
                //오른쪽 노드에서 1번째를 찾는 것으로 바뀜 (B - lNoode)
            }
        }
        //해당 idx에 도착했다면.
        update(node - base + 1, -1);//해당 노드 사탕을 빼면서
        cout << node - base + 1 << '\n';//해당 맛 출력 1번째 맛부터 시작함.


    }

    return 0;
}

 

 

여기서도 K번째를 찾기 위해서 전체를 100만개를 여러번 뒤지는 것은 비효율적이다.

그래서 tree를 이용한 것이다.