[백준 10775] 공항

 

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

10775번: 공항

1/6일 풀었던 문제

요구사항

1. 최대로 주차(?)할 수 있는 비행기 수 구하기

 

풀이

1. n번째가 차지하고 있으면 n-1번째가 비어있는가 검사한다.

Union Find자료구조를 이용한다.

#include <stdio.h>
#include <algorithm>
#include <list>
#include <iostream>

using namespace std;
 
struct NODE {
    int prev;
    int next;
    int val;
};
const int PN=23;
const int SIZE=100000;
int table[100001];

int parent[100001];
int Find(int x)
{
    if(parent[x]==x) return x;
    return parent[x]=Find(parent[x]);
}
void Union(int x, int y)
{
    x = Find(x);
    y = Find(y);
    if(x !=y){
        if(x<y){
            parent[y]=x;
        }
        else{
            parent[x]=y;
        }
    }
}

int main()
{
    int g,p;
    cin>>g>>p;
    for(int i=1 ; i <=g ; i++)
        parent[i]=i;
    int flag=0;
       int ans=0;
    for(int i=0 ; i < p ; i++){
        int x;
        scanf("%d",&x);
        if(flag==1)
        continue;
        int gate=Find(x);
    //    cout<<"gate "<<gate<<endl;

    
        if(gate==0){
            flag=1;
      //      cout<<"parent "<< parent[x]<<endl;
            //continue;
        }
        else{
            ans++;
            Union(gate,gate-1);
        //    cout<<"Union "<< parent[x]<<endl;
        }        
    }

    cout<<ans<<endl;
}