[ 백준 2243 ] 사탕상자 : C++ 풀이

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

2243번: 사탕상자

 

해설

세그먼트 트리 문제입니다.

 

  1. 자료의 수정이 많이 일어난다는 점

 

  2. 요구되는 숫자가 매우 크다는 점

 

을 미루어 보어 세그먼트 트리임을 알 수 있습니다.

 

세그먼트 트리 정의하기

이 문제에서 요구하는 점은 2가지입니다. 바로 구간 합의 내용을 뭘로 정해야하냐 와 query 방법을 생각해내는 발상을 요구하고 있습니다.

 

일단 트리 자체는 사실 문제에서 요구하는 숫자의 크기만 봐도 알 수는 있습니다. (이래서 문제를 잘 읽어야..) 사탕의 맛이 1부터 100만가지가 있고, 해당 맛 별로 몇개의 개수가 있는지 세그먼트 트리를 정하면 우리가 원하는 정보를 얻을 수 있습니다. 당연하지만, 사탕의 등수를 정하는 기준이 결국 사탕의 개수이기 때문이죠.

query 를 하는 방법 생각해내기

두번째는 Query 방식에서 요구되는 결과값 찾기입니다. 우리가 찾고자하는 정보는 사탕의 등수 입니다. 사탕의 개수가 아닙니다.

 

맛을 1부터 100만 까지를 구간 N으로 정의를 했기 때문에 저희가 i번째 사탕을 찾고자한다면, 이와 관련된 정보인 사탕의 개수를 통해 저희가 검색을 할 수 있을 것입니다. 아마 N번째 맛의 사탕을 찾고자 한 경우라면 문제가 많이 어려워졌을거같네요.

 

세그먼트 트리의 자식 중 왼쪽 자식일 수록 맛잇는 사탕(높은 등수) 를 나타내고, 오른 쪽 자식일수록 맛 없는 사탕(낮은 등수)를 가르킬 것입니다.

 

따라서 이를 통해 저희가 찾는 사탕을 검색할 수 있는데, 이는 세그먼트트리의 query보다는 사뭇 다른 양상을 보이는 이분탐색과도 같습니다. 일단 경우의 수를 생각해봅시다.

 

1번 경우입니다. 사탕의 개수가 10개 이고, 3번째로 맛있는 사탕을 찾고싶습니다. 근데 아래와 같은 상황이라고 칩시다.

 

이렇게 된다면 이미 3보다 큰 숫자 5 가 왼쪽 자식으로 등록되어 있으니, 3번째로 맛있는 사탕은 왼쪽 자식에 들어있음을 인지할 수 있습니다.

 

따라서 이때는 왼쪽 자식의 노드로 재귀 호출해주면 됩니다.

 

2번 경우입니다. 이같은 경우는 현재 내가 왼쪽 자식에서 찾고자하는 사탕을 못찾은 경우입니다.

이렇게 된다면 왼쪽 노드 중에 i 번째의 사탕은 없는 경우일 겁니다. 그러므로 오른쪽 자식에서 i 값에서 왼쪽 자식노드의 값을 뺀 1번째 사탕을 찾으면 됩니다.

 

query를 오른쪽 노드로 재호출하되, i 값을 왼쪽자식노드값에서 뺀 값을 넣으면 되는거죠.

 

또한 마지막으로 자식 노드가 둘중 하나가 0인 경우도 있을 겁니다. 이런 경우 0인 노드로 가는 것은 없는 사탕을 찾는 경우이므로, 반드시 0이 아닌 노드로 가게 만들어주면 됩니다.

 

마지막으로 사탕을 꺼내서 주기 때문에 저희가 찾아보는 모든 노드들의 크기를 1씩 빼주어야합니다. 저희가 찾아보는 노드 자체가 꺼낼 사탕이 존재하는 노드기 때문입니다.

 

update 방식

사탕의 개수를 바꿔치기 하는 경우는 저희가 첫번째 논지에서 언급한 세그먼트 트리 대로 구현이 되었다면, 일반적인 구현 방법대로 구현하면 됩니다.

 

소스코드

#include<iostream>
using namespace std;

int N;
const int candy_max = 1000000;
int seg[4000001]; // 사탕상자가 빈 상태로 시작.

int update(int nodeLeft, int nodeRight, int idx, int reval, int node) {
	// 2 옵션으로 넣고 빼는 경우.
	// 개수가 음수가 되는 경우가 없다했으므로 표현안함.
	// 사탕의 맛으로 검색하는 경우이므로 1 옵션과 다르다.
	if (nodeLeft > idx || nodeRight < idx) return seg[node];
	if (nodeLeft == nodeRight) return seg[node] = seg[node] + reval;
	int mid = (nodeLeft + nodeRight) / 2;
	return seg[node] = update(nodeLeft, mid, idx, reval, node * 2) + update(mid + 1, nodeRight, idx, reval, node * 2 + 1);
}

void query(int nodeLeft, int nodeRight, int idx, int node) {
	// 이 쿼리는 이분 탐색임.
	// query 와 동시에 update를 하는경우
	// 사탕의 등수로 검색
	if (nodeLeft == nodeRight) {
		cout << nodeLeft << '\n'; // 그래서 이게 몇번째 값인지 반환
		seg[node]--; // 개수 반환
		return;
	}
	if(seg[node]) seg[node]--;
	int mid = (nodeLeft + nodeRight) / 2;
	
	if (seg[node * 2] == 0) {
		query(mid + 1, nodeRight, idx, node * 2 + 1);
		return;
	}
	if (seg[node * 2 + 1] == 0) {
		query(nodeLeft, mid, idx, node * 2);
		return;
	}

	if (seg[node * 2] < idx) {
		query(mid + 1, nodeRight, idx - seg[node * 2], node*2 + 1);
		return;
	}
	query(nodeLeft, mid, idx, node*2);
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> N;
	int a, b, c;
	for (int i = 0; i < N; ++i) {
		cin >> a;
		if (a == 1) {
			cin >> b;
			query(1, candy_max, b, 1);
		}
		else {
			cin >> b >> c;
			update(1, candy_max, b, c, 1);
		}
	}
}