[백준 10775] 공항 (C++)

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

10775번: 공항

1. 주의할 점

- 현재 숫자 N을 기준으로 1~N중에서 비행기를 넣을 수 있는 가장 큰 번호의 게이트를 Par[]배열에 담는다 -> 검색할 때, 재귀를 통해 Log(n)의 시간복잡도를 가진다

 

2. 구현

- Par[i] = i로 1~게이트 최대 수 까지 초기화한다

- 입력받는 비행기를 Par[] 배열을 사용하여 Idx에 넣을 수 있다면, Cnt++ 이후에 Par[Idx] = Idx-1로 초기화 한다

- 만약 Idx가 0이라면 더 이상 비행기를 받지 못하므로 종료한다

 

#include <iostream>
using namespace std;
int par[100001];
bool finish = false;

int find_parent(int x) {
	if (par[x] == x) return x;
	return par[x] = find_parent(par[x]);
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int gate, airplane, val, cnt = 0;
	cin >> gate >> airplane;
	for (int i = 1; i <= gate; i++)
		par[i] = i;

	for (int i = 0; i < airplane; i++) {
		cin >> val;
		if (finish) continue;
		int idx = find_parent(val);		//집어 넣을 수 있는곳
		if (idx == 0) 
			finish = true;
		else {
			cnt++;
			par[idx] = idx - 1;
		}
	}
	cout << cnt;
	system("pause");
	return 0;
}