백준 2243 c++ "사탕상자" -PlusUltraCode-

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

 

[필자 사고]

 

세그먼트 자료구조를 이용하여 푸는 문제이다.

단순히 세그먼트 자료구조를 만드는 것에서 그치지 않고 응용이 들어갔따.

현재 4순위의 캔디를 뽑으세요 라고 주어지면 
세그먼트 트리의 탐색 방법은 왼쪽 자식 노드의 캔디 수가 현재 캔디수보다 작다면
왼쪽 자식으로 이동하고
그렇지 않으면 오른쪽으로 이동 및 4순위 캔디를 왼쪽자식캔디만큼 빼야된다.

세그먼트 트리는 많은 유형이 있다. 계속 반복해서 코드를 작성하다보면 감을 찾을것이다.

 

[코드 해설]

 

• 세그먼트 트리 초기화 및 입력 처리
  • 입력으로 게임에 사용될 데이터를 받습니다.
  • 세그먼트 트리를 tree라는 벡터로 초기화하며, 4 * MAX + 1 크기의 배열로 설정합니다.
• 명령 처리 로직
  • 총 N개의 명령이 입력으로 주어지며, 각각의 명령에 대해 다음과 같은 작업을 수행합니다:
    • 명령 1 (출력 및 감소)
      • 특정 순서에 해당하는 값을 찾습니다.
      • 세그먼트 트리의 Query 함수는 해당 값이 위치한 인덱스를 반환합니다.
      • 반환된 위치의 값을 Update 함수로 감소시킵니다.
      • 결과적으로 특정 순서에 해당하는 값을 빠르게 찾고 처리합니다.
    • 명령 2 (값 추가)
      • 특정 위치에 값을 추가하거나 감소시킵니다.
      • 이를 위해 Update 함수를 호출하여 세그먼트 트리의 해당 위치를 업데이트합니다.
• 세그먼트 트리 주요 함수 설명
  • Query 함수:
    • 현재 노드의 구간 합 데이터를 기반으로 특정 값이 위치한 인덱스를 찾는 역할을 합니다.
    • 재귀적으로 트리를 탐색하며, 값이 포함된 구간을 좁혀나갑니다.
  • Update 함수:
    • 특정 인덱스의 값을 업데이트하고, 해당 변경사항을 부모 노드에 전파합니다.
    • 구간의 시작과 끝을 기준으로 트리를 재귀적으로 업데이트합니다.
• 게임 시작
  • 입력 명령에 따라 Query와 Update를 사용해 데이터를 처리합니다.
  • Query로 값을 탐색하고, Update로 값을 변경하며 명령을 수행합니다.
  • 결과적으로, 주어진 입력에 따라 데이터 처리와 결과 출력이 이루어집니다.

 

[소스 코드]

#include <iostream>
#include <vector>
#define MAX 1000000
using namespace std;

int N;
vector<long> tree;

long Query(int Node, int start, int end, int num) {
	if (start == end) {
		return start;
	}

	int mid = (start + end) / 2;

	if (tree[Node*2] >= num) {
		return Query(Node * 2, start, mid, num);
	}
	else {
		return Query(Node * 2 + 1, mid + 1, end, num - tree[Node * 2]);
	}
}
void Update(int Node, int start, int end, int idx, int val) {
	if (idx<start || idx>end)return;

	tree[Node] += val;

	if (start != end) {
		int mid = (start + end) / 2;
		Update(Node * 2, start, mid, idx, val);
		Update(Node * 2 + 1, mid + 1, end, idx, val);
	}
}


void Game_Start() {
	cin >> N;
	tree.resize(4 * MAX + 1,0);

	for (int i = 0; i < N; i++) {
		int flag;
		cin >> flag;
		if (flag == 1) {
			int num;
			cin >> num;
			int pos = Query(1, 1, MAX, num);
			cout << pos << '\n';
			Update(1, 1, MAX, pos, -1);
		}
		else {
			int b, c;
			cin >> b >> c;
			Update(1, 1, MAX, b, c);
		}
	}
}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	Game_Start();
}