c언어 2243번 사탕상자 (백준)

#include <stdio.h>

int tree[4000004] = {};

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

void update(int s, int e, int node, int index, int dif) {
	if(index < s || index > e) return;
	tree[node] += dif;
	if(s==e) return;
	int mid = (s+e)/2;
	update(s, mid, node*2, index, dif);
	update(mid+1, e, node*2+1, index, dif);
}

int main(void) {
	int n,a,b,c;
	scanf("%d",&n);
	while(n--) {
		scanf("%d",&a);
		if(a==1) {
			scanf("%d",&b);
			c = find(1, 1e6, 1, b);
			printf("%d\n",c);
			update(1, 1e6, 1, c, -1);
		}
		else if(a==2) {
			scanf("%d %d",&b,&c);
			update(1, 1e6, 1, b, c);
		}
	} 
}

 

풀이 : 세그먼트 트리

 

1. 1~1000000 까지의 사탕의 개수를 세그먼트 트리 형식으로 담을 수 있는 배열을 생성합니다. (0으로 초기화)

2. 초기화 함수는 필요 없고, 탐색, 갱신 함수만 만들어 줍니다.

 

3. 갱신 함수는 여러 세그먼트 트리문제와 동일하게 누적합을 기반으로하여 갱신해 주면 됩니다.

 

4. 탐색함수가 이 문제에서 가장 핵심적인 부분 입니다.

x번째 사탕이 어디 있는지 (무엇인지)를 알아야 하기 때문에

왼쪽 자식노드의 값이 x 이상이면 왼쪽 노드에 찾고 있는 사탕이 있다는 것이며

왼쪽 자식노드의 값이 x 미만이면 오른쪽 노드에 찾고 있는 사탕이 있다는 의미 입니다.

 

왼쪽 자식노드로 탐색을 이어 갈 때는 x 값을 그대로 유지하면 되지만

오른쪽 자식노드로 탐색을 이어 갈 때는 x값에 왼쪽 자식노드의 값을 빼준 상태로 이어가야 합니다.

 

이를 반복하다보면 범위가 start == end (즉 1개) 로 좁혀지게 됩니다. 이것이 찾고자 하는 값입니다.

 

5. query는 두가지가 주어집니다.

 1이 주어지면 원하는 것을 발견하고, 그것을 1 감소 시킵니다.

 2가 주어지면 원하는 만큼 특정 사탕의 개수를 수정합니다.