[JAVA / 백준 : 10775] 공항

조건

g번 비행기는 g번 이하 게이트에만 도킹이 가능하다

g번비행기를 g번 게이트에 도킹하는 것이 최선.

g번 비행기를 g번 게이트에 도킹할 수 없다면, g-1번 게이트에 차선책으로도킹시킴. g-2, ... 0번까지 탐색

차선책이 0번을 가리키고 있으면 도킹할 수 없는 상태!

---

import java.util.Scanner;

public class Main {
	static int[] parent;
	public static void union(int x, int y) {
		x = find(x);
		y = find(y);
		
		if(x != y)
			parent[x] = y;
	}
	public static int find(int x) {
		if(x == parent[x])
			return x;
		return parent[x] = find(parent[x]);
	}
	public static void main(String[] args) {
	
		Scanner scan = new Scanner(System.in);
		int G = scan.nextInt();
		int P = scan.nextInt();
		parent = new int[G + 1];
		for(int i = 1; i <= G; i++)
			parent[i] = i;
		
		int ans = 0;
		for(int i = 0; i < P; i++) {
			int g = scan.nextInt();
			int emptyGate = find(g);
			
			if(emptyGate == 0)
				break;	//하나라도 못넣는게 생기면 끝남
			ans++;
			//차지된 곳은 -1을 차선책으로
			union(emptyGate, emptyGate - 1);
		}
		System.out.println(ans);
		scan.close();
	}

}

find랑 union으로 사용하는 문제가 처음이였다

앞으로 이런 문제가 나오면 잘 풀자!!