공항

 

이것도 그리디적인 해결 방법이 들어가는데, 1~g(i)번째 게이트중 하나에 도킹해야 한다면, g(i)부터 보면서 갈 수 있는 게이트 중

최대한 큰 번호의 게이트에 도킹해야 한다.

그런데 이걸 그냥 단순 for문으로 구현하면, 최대 g(i)번 탐색을 해야 하니까 시간복잡도가 GP가 되기 때문에 안된다.

따라서 도킹을 하면 했다고 체크를 하고, 번호를 탐색하면서 최대 번호를 찾는 방식 말고 다른 방식을 사용해야 한다.

g(i)가 들어왔을 때 결국 1~g(i)중 남아있는 번호의 최대를 구해야 한다.

 

이를 잘 생각해보면 한가지 알고리즘이 떠오른다.

세그먼트 트리를 이용하면, 구간별로 max값을 쉽게 탐색할 수도 있고 update도 빠르게 할 수 있다.

#include<stdio.h>
#include<algorithm>
using namespace std;
int G,P;
int gate[100004];
int seg[300004];
int arr[300004];
int finds(int s, int e, int fs, int fe, int n)
{
    if(s>fe || e<fs) return 0;
    if(fs<=s && e<=fe) return seg[n];
    int m = (s+e)/2;
    return max(finds(s,m,fs,fe,n*2),finds(m+1,e,fs,fe,n*2+1));
}
int init(int s, int e, int n)
{
    if(s==e)
    {
        seg[n] = arr[s];
        return seg[n];
    }
    int m = (s+e)/2;
    int p=init(s,m,n*2);
    int q=init(m+1,e,n*2+1);
    seg[n] = max(p,q);
    return seg[n];
}
void update(int s, int e, int n, int v, int p)
{
    if(p<s || p>e) return;
    seg[n]=max(seg[n],v);
    if(s==e)
    {
        seg[n]=v;
        return;
    }
    int m = (s+e)/2;
    update(s,m,n*2,v,p);
    update(m+1,e,n*2+1,v,p);
    return;
}
int main()
{
    scanf("%d",&G);
    scanf("%d",&P);
    int ans=0;
    for(int i=1;i<=G;i++) arr[i]=i;
    for(int i=1;i<=P;i++) scanf("%d",&gate[i]);
    init(1,G,1);
    for(int i=1;i<=P;i++)
    {
        int x = finds(1,G,1,gate[i],1);
        if(x == 0)
        {
            ans = i;
            break;
        }
        arr[x]=0;
        init(1,G,1);
    }
    printf("%d",ans-1);
}

기껏 힘들게 구현해놨더니 시간 초과가 뜬다.

find랑 init 한번에 log(n)의 시간이 걸리니까 Plog(G)이면 시간초과가 날리가 없는데 왜 나는지 도저히 모르겠다.

예제 데이터도 다 잘 출력되는데 이상해서 일단 그냥 한번 올려봤다.

 

결국 모르겠어서 풀이를 검색해봤더니 union-find를 쓰는 문제였다.

아이디어가 신기한 문제인거 같은데 도킹 게이트 g[i]가 입력되면 g[i]의 그룹과 그 번호-1을 그룹화시키는 방식이다.

여러 풀이를 봤지만 나도 처음엔 이해가 잘 안됐다.

그나마 이해를 시켜준 것이 이 그림이다.

for(int i=1;i<=P;i++)
    {
        int x;
        scanf("%d",&x);
        int doc = fin(x);
        if(doc!=0)
        {
            uni(doc, doc-1);
            ans++;
        }
        else break;
    }

핵심 코드는 이 부분이다.

입력된 도킹 게이트 x의 부모를 찾고 doc와 doc-1을 union 시킨다.

 

세그트리가 왜 안되는지는 아직 모르겠지만 아무튼 유니온-파인드로 기발하게 풀 수 있었다.

#include<stdio.h>
int G,P;
int group[100004];
int fin(int x)
{
    if(x==group[x]) return x;
    group[x]=fin(group[x]);
    return group[x];
}
void uni(int a, int b)
{
    int ga = fin(a);
    int gb = fin(b);
    if(ga > gb)
    {
        group[ga] = group[gb];
    }
    else if(ga < gb)
    {
        group[gb] = group[ga];
    }
    return;
}
int main()
{
    scanf("%d",&G);
    scanf("%d",&P);
    int ans=0;
    for(int i=1;i<=G;i++) group[i]=i;
    for(int i=1;i<=P;i++)
    {
        int x;
        scanf("%d",&x);
        int doc = fin(x);
        if(doc!=0)
        {
            uni(doc, doc-1);
            ans++;
        }
        else break;
    }
    printf("%d",ans);
}