BOJ 10775 공항

출처 : https://www.acmicpc.net/problem/10775

한 6개월전 union-find 분류 훑다가 문제 이해가 안대서 넘겼는데

오늘 다시 보니깐 union-find풀이방법은 생각 안나고 이상하게 segment tree풀이가 생각났다.

간단한 설명 :
i번째 비행기가 k번쨰 게이트에 도킹하고 싶다.
지금 k번째 게이트가 비어 있다면 도킹하면 된다.

그러나 k번쨰 게이트가 이미 도킹된 상태라면
1 ~ k - 1번쨰 게이트에 세우면 되는데 되도록 큰 숫자를 가지는 게이트에 세워야 한다.
(미안... 솔직히 증명은 몬하겠는데 사실 이러면 안되는데 직관이 넘 쎄게 들어옴..)

그래서 내가 새로 도킹할 게이트 번호를 p라 하자
p를 구하기 위해서는 우선 1 ~ k - 1 까지 비어있는 게이트 수를 구하자
(여기서 비어있는 게이트 수를 s라 하자)

만약 s가 0 이면 더이상 세울 수 있는 게이트의 수가 0이니 종료를 하고

0이 아니라면 비어있는 게이트중 s번째 비어있는 게이트를 찾으면 된다.

말이 좀 어색한데 코드를 보면 이해가 될것이다.

#include<stdio.h>
#include<malloc.h>
int answer, *tree, *list;
int make_answer();
int qu(int, int, int, int, int);
void update(int);
int kth(int, int, int, int);
int main(void)
{
	answer = make_answer();
	printf("%d\n", answer);
	return 0;
}
int make_answer()
{
	int gn, an, i, node, s, e, l, r, g, t, ans, idx;
	scanf("%d", &gn);
	scanf("%d", &an);
	for (i = 0, list = (int *)malloc(sizeof(int) * an); i < an; i++)
	{
		scanf("%d", &list[i]);
	}
	for (node = s = l = r = 1; r - l + 1 < gn; l <<= 1, r <<= 1, r |= 1);
	for (tree = (int *)calloc(r + 1, sizeof(int)), g = l - 1, e = r - l + 1, i = l; i <= r; i++)
	{
		tree[i] = 1;
	}
	for (i = g; i; i--)
	{
		tree[i] = tree[i << 1] + tree[i << 1 | 1];
	}
	for (i = ans = 0; i < an; i++)
	{
		t = list[i];
		if (tree[g + t] == 1)
		{
			ans++;
			update(g + t);
			continue;
		}
		t = qu(node, s, e, 1, t - 1);
		if (t)
		{
			ans++;
			idx = kth(node, s, e, t);
			update(idx + g);
		}
		else
		{
			break;
		}
	}
	free(tree);
	free(list);
	return ans;
}
void update(int idx)
{
	tree[idx] = 0;
	idx >>= 1;
	while (idx)
	{
		tree[idx] = tree[idx << 1] + tree[idx << 1 | 1];
		idx >>= 1;
	}
}
int qu(int node, int start, int end, int left, int right)
{
	int mid;
	if (left > end || right < start)
	{
		return 0;
	}
	if (left <= start && end <= right)
	{
		return tree[node];
	}
	mid = (start + end) >> 1;
	return qu(node << 1, start, mid, left, right) + qu(node << 1 | 1, mid + 1, end, left, right);
}
int kth(int node, int start, int end, int k)
{
	int mid;
	if (start == end)
	{
		return start;
	}
	mid = (start + end) >> 1;
	if (tree[node << 1] >= k)
	{
		return kth(node << 1, start, mid, k);
	}
	else
	{
		return kth(node << 1 | 1, mid + 1, end, k - tree[node << 1]);
	}
}