[백준] 10775번 공항 C++

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

10775번: 공항

들어오는 g번 비행기는 1번부터 g번째 게이트중 하나에 도킹할 수 있다.

그리디하게 g번부터 g-1, g-2로 채워나가야 더 많은 비행기를 도킹할 수 있음을 알 수 있다.

g번 비행기가 g번이 아닌 1번 게이트에 도킹한다면 모든 비행기가 1번에 도킹할 기회가 없어지는 것이고

g번 비행기가 g번 게이트에 도킹한다면 g번~G번 비행기가 g번에 도킹할 기회가 없어지기 때문이다.

 

따라서 모든 비행기들은 자신의 번호 g부터 g-1,g-2,g-3...,1 까지 선형탐색으로 빈자리에 찾아들어가면 될 것이다.

그러나 비행기의수 10^5에 선형탐색 10^5는 시간초과가 발생한다.

자신이 들어가야할 게이트를 바로 알 수 있도록 유니온 파인트를 이용한다.

 

처음에는 모든 게이트가 자기 자신이 부모이다.

유니온 파인드의 find연산은 자신의 부모를 찾는다. 자기자신이 부모이니 처음에는 자신을 반환할 것이다.

 

1,2,3,4,5 게이트가 있을 때 4번 비행기가 도착했다고 하자 find(4)를 호출하면 4는 현재 자기자신이 리턴될 것이다.

따라서 4번 게이트에 도킹을 하고 4번과 3번을 merge한다. (숫자가 낮은쪽이 부모가 되도록)

1,2,3,4,5(4번의 부모는 3번 나머지 번호는 자기자신이 부모)

이 때 3번 비행기가 도착하여 동일한 시퀀스로 3번 게이트를 채웠다면 (3번 게이트에 도킹, 3번과 2번 merge)

1,2,3,4,5(3,4번의 부모는 2번 나머지는 자기 자신) 이런 형태일 것이다.

 

여기서 4번 비행기가 도착한다면 find(4)를 통해 2가 반환될 것이다. 이를 통해 순차탐색보다 적은 시간복잡도로 게이트를 찾을 수 있게 된다.

 

+추가

위와 같은 케이스에서 find연산을 최적화하지 않고 구현 시 O(N)이다.

그러나 메모이제이션을 이용하면 처음 탐색시에는 O(N)이지만 갱신 된 후에는 훨씬 짧은 시간 복잡도를 가진다.

 

#include<iostream>
#include<algorithm>
#include<unordered_map>
#include<cstring>
#include<math.h>
#include<queue>
#include<vector>

using namespace std;

int u[100001];

int find(int a) {
	if (u[a] < 0)return a;
	return u[a] = find(u[a]);
}

void merge(int a, int b) {
	a = find(a);
	b = find(b);
	if (a == b)return;

	//낮은 공항이 부모가 되도록 병합
	if (a < b) {
		u[a] += u[b];
		u[b] = a;
	}
	else {
		u[b] += u[a];
		u[a] = b;
	}
}


int main(void)
{
	ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

	memset(u, -1, sizeof(u));

	int G, P;
	cin >> G >> P;
	int count = 0;

	for (int i = 0; i < P; i++) {
		int g; cin >> g;

		g = find(g);
		if (g == 0) {
			break;
		}
		merge(g, g - 1);
		count++;
	}

	cout << count;


}