반응형
728x170
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를 이용한 것이다.
728x90
반응형
그리드형
'문제풀이(Problem Solving)' 카테고리의 다른 글
백준, BOJ, 5573번, 산책 : C++ [CPP] (0) | 2022.01.07 |
---|---|
백준, BOJ, 5568번, 카드 놓기 : C++ [CPP] (0) | 2022.01.07 |
백준, BOJ, 1713번, 후보 추천하기 : C++ [CPP] (0) | 2022.01.06 |
백준, BOJ, 1665번, 가운데를 말해요 : C++ [CPP] (0) | 2022.01.05 |
백준, BOJ, 1062번, 가르침 : C++ [CPP] (0) | 2022.01.04 |