(BOJ) 10775 공항

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

 

문제 설명:

G개의 게이트가 있고, P개의 비행기가 순서대로 도착할 예정이다. 

도착한 비행기에게 주어진 값 gi이하의 게이트에만 비행기를 도킹할 수 있고,

이미 다른 비행기가 도킹한 곳에 도킹할 수 없다.

그리고

"이렇게 공항을 운영할 경우 간혹 비행기가 어떤 곳에도 도킹하지 못하는 사고가 발생한다. 이러한 사고가 일어나면 공항의 평판이 급속히 나빠져, 이후 어떤 비행기도 도착하지 않으려 할 것이다."

ㄴ> 어떤 곳에도 도킹하지 못하게 되면 지금껏 도킹한 비행기 수 출력하고 끝!

 

 

문제 풀이:

일단 가장 많이 비행기를 도킹하려면 도킹 할 수 있는 곳 중 가장 큰 수의 게이트에 도킹해야한다.

주어진 gi부터 1까지 빈 곳을 항상 다 찾으면 오래 걸리니까 다음 도킹 가능한 곳을 기록한다. <- union-find

만약 gi=3인 비행기가 들어왔다면 p[3]=2;를 해준다 (다음에 또 gi=3인 비행기가 들어오면 2번 gate에 도킹 가능하다는 뜻)

그 후, gi=2인 비행기가 들어왔다면 p[2]=1, 또 gi=2인 비행기가 들어왔다면 p[1]=0;

p[2]가 아니라 p[1]인 이유는 현재 비행기가 도킹한 곳이 p[1]이기 때문!

다음에 gi가 3이하인 비행기가 들어오면 find(gi)한 값은 0일 것이다. 0이면 도킹 가능한 곳이 없다는 뜻이므로 현재까지 도킹한 비행기 수 출력하고 리턴

 

 

소스코드:

int n, m,p[100001],cnt;

int find(int x) {
	if (p[x] < 0) return x;
	return p[x]=find(p[x]);
}

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

	cin >> n >> m;
	memset(p, -1, sizeof(p));
	for (int i = 0; i < m; i++) {
		int a;
		cin >> a;
		int tmp = find(a);
		if (tmp == 0) break;
		cnt++;
		p[tmp] = tmp - 1;
	}
	cout << cnt << '\n';
	return 0;
}