📖 백준 10775번 : https://www.acmicpc.net/problem/10775
조건
| 시간 제한 | 메모리 제한 |
|---|---|
| 1 초 | 256 MB |
문제
오늘은 신승원의 생일이다.
박승원은 생일을 맞아 신승원에게 인천국제공항을 선물로 줬다.
공항에는 G개의 게이트가 있으며 각각은 1에서 G까지의 번호를 가지고 있다.
공항에는 P개의 비행기가 순서대로 도착할 예정이며, 당신은 i번째 비행기를 1번부터 gi (1 ≤ gi ≤ G) 번째 게이트중 하나에 영구적으로 도킹하려 한다. 비행기가 어느 게이트에도 도킹할 수 없다면 공항이 폐쇄되고, 이후 어떤 비행기도 도착할 수 없다.
신승원은 가장 많은 비행기를 공항에 도킹시켜서 박승원을 행복하게 하고 싶어한다. 승원이는 비행기를 최대 몇 대 도킹시킬 수 있는가?
입력
첫 번째 줄에는 게이트의 수 G (1 ≤ G ≤ 10^5)가 주어진다.
두 번째 줄에는 비행기의 수 P (1 ≤ P ≤ 10^5)가 주어진다.
이후 P개의 줄에 gi (1 ≤ gi ≤ G) 가 주어진다.
출력
승원이가 도킹시킬 수 있는 최대의 비행기 수를 출력한다.
풀이
비행기의 번호에 따라 도킹이 가능한 게이트의 범위를 알 수 있다. 이 범위에서 도킹이 가능한 가장 큰 자리에 위치시키면 가장 많은 비행기를 공항에 도킹할 수 있다. 공항에 들어오는 비행기의 번호에 따라 예를 들어 gi가 4라면 (1~4)사이의 게이트에 도킹이 가능한 비행기라는 뜻이다. 따라서 각 비행기가 도킹할 수 있는 가장 큰 번호를 가진 게이트에 반복적으로 도킹시켜주면 된다.
단순하게 생각했을 때는, 10만개의 원소를 가지는 boolean배열을 만들어서 게이트의 도킹 가능 여부를 의미하게 만든다. gi의 번호에 맞는 boolean배열의 값을 true로 만들어주고 만약 값이 false라면 리니어하게 탐색해서 도킹할 수 있는 가장 큰 게이트를 찾아서 그 boolean값을 false로 바꿔 채워준다. 이 방식으로 게이트를 채우고 더 이상 위치시킬 게이트가 없다면 끝내고 반복된 횟수를 출력하면 끝이다. 하지만 O(N^2)에 가까운 시간복잡도를 가지는 로직이라 입력값이 최대 100,000이 주어지므로 적절하지 못하다.
유니온-파인드 알고리즘을 활용해서 비행기가 연속적으로 도킹되어 있는 게이트들을 하나의 집합으로 만들면 시간 내에 풀 수 있다. 각 집합의 루트가 현재 입력값보다 작은 것 중 가장 가까운 곳에 배치가능한 게이트의 번호를 가르키게 만들어 도킹하는 방식이다. gi를 입력 받을 때마다 gi에 해당하는 집합이 더 합쳐질 수 있는지 확인하고 gi-1과 Union해준다. 그럼 gi는 gi-1이 가지는 값을 가르키게 된다. 이를 반복해주고 반복한 횟수를 출력하는 방식이다.
코드
#include <iostream>
using namespace std;
int parent[100001];
int Find(int x) {
if (x == parent[x]) return x;
return parent[x] = Find(parent[x]);
}
void Union(int x, int y) {
x = Find(x);
y = Find(y);
if (x == y) return;
if (x > y) parent[x] = y;
else parent[y] = x;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
int plane;
int g, p;
cin >> g >> p;
for (int i = 0; i <= g; i++) parent[i] = i;
int ans = 0;
for (int i = 0; i < p; i++) {
cin >> plane;
plane = Find(plane);
if (plane == 0) break;
Union(plane, plane - 1);
ans++;
}
cout << ans;
return 0;
}