[ BOJ 백준 10775번 - 공항 ] 해설 및 코드

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

 

목적

i번째 비행기를 1번부터 gi (1 ≤ gi ≤ G) 번째 게이트중 하나에 도킹시키자.

 

접근법

1. 탐욕적으로 접근하자. 비행기를 최대한 gi에 가깝게 도킹시켜야 최대한 많은 비행기를 도킹시킬 수 있을 것이다.

2. 도킹할 게이트의 위치를 찾기 위해서 하나의 배열이 필요하다. i번째 게이트가 도킹에 사용되었다면, 다음으로 도킹 가능한 게이트를 가리키는 용도이다. Disjoint-set의 루트노드를 찾는 함수를 사용하면 될 것이다.

 

#include<bits/stdc++.h>
#define f(i,l,r) for(int i=l;i<=r;i++)
using namespace std;
 
int a[100001];
 
int find(int i){
    while(i!=a[i])a[i]=a[a[i]],i=a[i];
    return i;
}
 
int main(){
    ios_base::sync_with_stdio(0);
    
    int g,p;cin>>g>>p;
    f(i,1,g)a[i]=i;
    int i,ans=0;
    while(p--){
        cin>>i;
        if(!(i=find(i))){
            while(p--)cin>>i;
            break;
        }
        --a[i];
        ++ans;
    }
    cout<<ans;
    return 0;
}
 

 

문제 설명과 코드에 대한 피드백은 언제나 환영합니다.

 다양한 의견 댓글로 남겨주세요.