[백준/BOJ] 백준 2243번 : 사탕상자

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

2243번: 사탕상자

vector<int> candy(1000001, 0); ([사탕의 맛] = 개수)을 세그먼트 트리를 통해 나타냈고, 이분 탐색을 통해 원하는 사탕 순위를 만족하는 사탕의 맛을 구한다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int n;
vector<int> candy(1000001, 0); //[사탕의 맛] = 개수
vector<int> sgmtt(4000001, 0); //세크먼트 트리의 크기를 넉넉하게 1000000(사탕 맛 수치의 최댓값) * 4로 했다
int a, b, c;
vector<int> output;

int Update(int here, int index_left, int index_right, int update_index)
{
	if (index_left == index_right && index_right == update_index)
	{
		return sgmtt[here] = candy[update_index];
	}

	if (update_index < index_left || index_right < update_index)
		return sgmtt[here];

	int left_child = (here * 2) + 1;
	int right_child = (here * 2) + 2;
	int index_mid = (index_left + index_right) / 2;

	return sgmtt[here] = Update(left_child, index_left, index_mid, update_index) + Update(right_child, index_mid + 1, index_right, update_index);
}

int Query(int here, int index_left, int index_right, int find_left, int find_right)
{
	if (find_right < index_left || index_right < find_left)
		return 0;

	if (find_left <= index_left && index_right <= find_right)
		return sgmtt[here];

	int left_child = (here * 2) + 1;
	int right_child = (here * 2) + 2;
	int index_mid = (index_left + index_right) / 2;

	return Query(left_child, index_left, index_mid, find_left, find_right) + Query(right_child, index_mid + 1, index_right, find_left, find_right);
}

//index까지 범위에서 candy_rank순위의 사탕을 꺼낼 수 있는지 확인
bool Check(int index, int candy_rank)
{
	if (Query(0, 1, 1000000, 1, index) >= candy_rank)
		return true;

	return false;
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> n;

	for (int i = 0; i < n; i++)
	{
		cin >> a;

		//사탕을 꺼내는 경우
		if (a == 1)
		{
			cin >> b;

			int left = 1;
			int right = 1000000;
			int result = -1;

			while (left <= right)
			{
				int mid = (left + right) / 2;

				if (Check(mid, b) == true)
				{
					result = mid;

					right = mid - 1;
				}

				else
				{
					left = mid + 1;
				}
			}

			candy[result]--;
			Update(0, 1, 1000000, result);

			output.push_back(result);

		}

		//사탕을 넣는 경우
		else if (a == 2)
		{
			cin >> b >> c;

			candy[b] += c;
			Update(0, 1, 1000000, b);
		}


	}

	for (int i = 0; i < output.size(); i++)
		cout << output[i] << "\n";

	return 0;
}