티스토리 뷰

알고리즘 관련/BOJ

BOJ)10775 공항

JASON 자손9319 2017. 1. 4. 18:25

문제: icpc.me/10775


비행기가 도착하는 순서대로 게이트에 도킹을 하는데 한 게이트에는 오직 한대의 비행기만 도킹이 가능하다


이때 각각의 비행기는 1~g번째 게이트중 하나에 도킹할 수 있다는 정보가 들어올 때 최대로 도킹할 수 있는 비행기의 수를 출력하면 된다.


g번째 게이트부터 도킹을 하는게 이득인 것임은 자명하므로 disjoint-set을 이용하여 g게이트에 도킹이 될 경우 다시 g게이트를 확인 할 때 g-1게이트를 확인 하도록 parent를 설정해주면 된다.


만약 find 호출에서 0을 호출하게 된다면 1~g번째 게이트는 모두 사용중인것이니 더 이상 도킹이 불가능 하므로 현재까지 도킹 된 횟수를 출력해 주면 된다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <cstdio>
#include <algorithm>
using namespace std;
int par[100010], g, p, t, v, ans;
int find(int x) {
    if (x == par[x])return x;
    return par[x] = find(par[x]);
}
int main() {
    scanf("%d%d"&g, &p);
    for (int i = 0; i <= g; i++)
        par[i] = i;
    for (int i = 0; i < p; i++) {
        scanf("%d"&t);
        v = find(t);
        if (!v)break;
        par[v] = v - 1;
        ans++;
    }
    printf("%d\n", ans);
    return 0;
}
cs


'알고리즘 관련 > BOJ' 카테고리의 다른 글

BOJ)1865 웜홀  (0) 2017.01.05
BOJ)11999 Milk Pails  (2) 2017.01.05
BOJ)10775 공항  (0) 2017.01.04
BOJ)12845 모두의 마블  (0) 2017.01.03
BOJ)12846 무서운 아르바이트  (0) 2017.01.03
BOJ)12844 XOR  (0) 2017.01.03
댓글
댓글쓰기 폼