[백준] 10775 - 공항

[문제링크]

10775번: 공항

 

0. 비행기가 1~n의 게이트 중 하나에 들어가야한다면, 가능한 게이트 중 가장 큰 게이트에 들어가야한다 (그리디)

  - 1~n이 가능한 비행기가 1번에 들어가버리면, 1~1밖에 안되는 비행기가 다음에 들어오면 즉시 종료된다

 

1. 비행기가 가능한 가장 큰 게이트에 들어가므로, 게이트들은 연속으로 차지되게 된다

  - 1~n인 비행기만 5대 들어왔다면 n, n-1, n-2, n-3, n-4 게이트가 순서대로 사용될 것

 

2. 각 게이트들을 독립된 집합으로 두고, 비행기가 들어올때마다 바로 앞 집합과 합쳐나가며 연산한다

  - 바로 앞 집합인 이유는, n에 다른 비행기가 또 찾아올 경우 그 앞을 탐색해야하기 때문

  - n이 사용되면 n-1, n-1이 사용되면 n-2 ...

 

3. 대표자가 큰 쪽이 작은쪽에 합쳐지도록 하면 대표자가 "가장 작은 값 = 다음에 사용될 값"을 나타내게 할 수 있다.

  - n, n-1, n-2, n-3, n-4 게이트가 이미 사용중이라면, 이 집합의 대표자는 n-5

  - 1~n인 비행기가 다시 들어온다면, root(n) = n-5를 반환해준다

  - n-5를 사용한 후 n-6번 집합과 합쳐준다

  - n-6번이 이미 n-7, n-8번과 집합을 이루고 있었다면?

  - n-6번 집합의 대표자는 n-9, n-5집합의 대표자는 n-5이므로 큰쪽 n-5에서 작은쪽 n-9를 부모로 사용한다

 

4. 1~n의 모든 게이트가 사용중이라면, 1~n이 하나의 집합을 이루고 있다는 것이다

  - 대표자는? 0이다

 

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main{
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = pint(br.readLine());
		int P = pint(br.readLine());
		int cnt=0;
		init(N);
		for (int i = 0; i < P; i++) {
			int g = pint(br.readLine());
			
			int gate=find(g);
			if(gate==0) {
				break;
			}
			else {
				merge(gate-1,gate);
				cnt++;
			}
		}
		System.out.println(cnt);
	}
	static int[] parents;
	
	static void init(int N) {
		parents=new int[N+1];
		for (int i = 0; i < N+1; i++)parents[i]=i;
	}
	
	static int find(int n) {
		if(parents[n]!=n)return parents[n]=find(parents[n]);
		return n;
	}
	
	static void merge(int n, int m) {
		int rn=find(n), rm=find(m);
		if(rn==rm)return;
		parents[rm]=rn;
	}
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

결과 화면