[BOJ/Gold 2] 백준 10775 공항(C++)

문제 링크

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

10775번: 공항

 

문제

오늘은 신승원의 생일이다.

박승원은 생일을 맞아 신승원에게 인천국제공항을 선물로 줬다.

공항에는 G개의 게이트가 있으며 각각은 1에서 G까지의 번호를 가지고 있다.

공항에는 P개의 비행기가 순서대로 도착할 예정이며, 당신은 i번째 비행기를 1번부터 gi (1 ≤ gi ≤ G) 번째 게이트중 하나에 영구적으로 도킹하려 한다. 비행기가 어느 게이트에도 도킹할 수 없다면 공항이 폐쇄되고, 이후 어떤 비행기도 도착할 수 없다.

신승원은 가장 많은 비행기를 공항에 도킹시켜서 박승원을 행복하게 하고 싶어한다. 승원이는 비행기를 최대 몇 대 도킹시킬 수 있는가?

입력

첫 번째 줄에는 게이트의 수 G (1 ≤ G ≤ 105)가 주어진다.

두 번째 줄에는 비행기의 수 P (1 ≤ P ≤ 105)가 주어진다.

이후 P개의 줄에 gi (1 ≤ gi ≤ G) 가 주어진다.

출력

승원이가 도킹시킬 수 있는 최대의 비행기 수를 출력한다.

예제 입력 1

4
3
4
1
1

예제 출력 1

2

예제 입력 2

4
6
2
2
3
3
4
4

예제 출력 2

3

힌트

예제 1 : [2][?][?][1] 형태로 도킹시킬 수 있다. 3번째 비행기는 도킹시킬 수 없다.

예제 2 : [1][2][3][?] 형태로 도킹 시킬 수 있고, 4번째 비행기는 절대 도킹 시킬 수 없어서 이후 추가적인 도킹은 불가능하다.

알고리즘 분류

• 그리디 알고리즘

풀이

도킹이 가능한 게이트면 유니온 파인드를 사용하여 바로 앞 게이트와 묶어준다. 이렇게 하면 g가 주어졌을 때 몇 번째 게이트에 도킹할 수 있는 지 확인할 수 있다.

도킹이 불가능한 게이트라면 반복문을 바로 종료하고 게이트에 도킹한 비행기의 수를 출력한다.

그리디하게 접근하는 방법은 생각했지만 그냥 구현하면 시간 제한에 걸릴 것 같아서 찾아보니 유니온 파인드를 이용하여 바로 앞 게이트와 묶어준다는 기막힌 방법이 있었다.

코드

#include <iostream>
#include <string>
#include <cmath>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#include <algorithm>
#include <climits>
#define FASTIO cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define MAX 100001
#define LL long long
#define INF 1e9

using namespace std;
int G, P, g;
int Parent[MAX];
vector<int> Vec;
int answer = 0;

void Init() {
	for (int i = 1; i <= G; i++) {
		Parent[i] = i;
	}
}

int Find(int X) {
	if (Parent[X] == X) {
		return X;
	}
	return Parent[X] = Find(Parent[X]);
}

void Union(int X, int Y) {
	int PX = Find(X);
	int PY = Find(Y);
	if (PX != PY) {
		Parent[PY] = PX;
	}
}

void Input() {
	cin >> G;
	Init();
	cin >> P;
	for (int i = 0; i < P; i++) {
		cin >> g;
		Vec.push_back(g);
	}
}

void Find_Answer() {
	for (int i = 0; i < P; i++) {
		int f = Find(Vec[i]);
		if (f != 0) {
			Union(f - 1, f);
			answer++;
		}
		else {
			break;
		}
	}
	cout << answer << "\n";
}

int main() {
	FASTIO
	Input();
	Find_Answer();

	return 0;
}