급하게임개발

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

이제 백준 티어가 3  넘어가면서 부터 알고리즘이 하나만 쓰이는게 아니라 여러개 가 섞여 쓰이는게 보이기 시작한다 이문제의 경우 일단 그리디 적으로 하기위해서는 내가 들어갈 수 있는 애중에 가장 큰곳에 들어가야 한다 그러면 내가 들어갈 수 있는곳중 큰곳을 어떻게 구할까가 문제인데 이부분을 유니온 파인드로 만들어 줘야한다.
즉 우리는 비행기들의 그룹을 만들어 줘야한다

해당 인풋을 예시로 생각해 보자
현재 게이트는 1번 2번 3번 4번 이있다
4번 비행기는 4번에 들어가는게 가장 알맞다 그 이후는 이후에 들어올 비행기들이 작을 경우에 작은 비행기들이 들어갈 확률이 적기 때문이다

이에 4 이상의 번호인 비행기들이 다음에 들어갈 수 있는 영역인 3번 비행기의 영역과 묶는 다 만약에 이전에 3번 이하 비행기가 들어와있으면 3번 비행기그룹도 이미 만들어 져있을 것이니까 유니온 파인드를 통해 해당 그룹을 묶어준다

#include<iostream>
#include<algorithm>
using namespace std;
int parent[100000];
int arr[100000];
int g, p;
int Find(int x) {
	if (parent[x] == x)
		return x;
	else
		return parent[x] = Find(parent[x]);
}

void Union(int x, int y) {
	int parentX = Find(x);
	int parentY = Find(y);
	if (parentX > parentY) {
		swap(parentX, parentY);
	}
	parent[parentY] = parentX;
}
int main() {
	cin.tie(NULL);
	cout.tie(NULL);
	ios::sync_with_stdio(false);
	cin >> g;
	cin >> p;
	int n;
	int answer = 0;
	for (int i = 0; i < p; i++) {
		cin >> arr[i];
	}
	for (int i = 1; i <= g; i++) {
		parent[i]=i;
	}

	for (int i = 0; i < p; i++) {
		int f = Find(arr[i]);
		if (f != 0) {
			Union(f - 1, f);
			answer++;
		}
		else {
			break;
		}
	}

	cout << answer;
}