Saturday, August 1, 2015

KOI 2005 고등부 3번 - 소방차

문제 링크
우선 가장 쉬운 건 O(NM)의 dynamic programming.
D(i, j) = min(D(i-1, j), D(i,j-1), D(i-1,j)+|P(i)-F(j)|).
D(i-1, j)랑 D(i, j-1)을 참조할 때는 min(i-1, j-1)+1과 같은 지 확인하면서 compute하면 된다.

그런데 사실 해법은 dynamic programming과는 다르게 greedy method이다.

펌프 2개 P1<P2가 있고, 소방차 2개 F1<F2가 있다고 하자.
만약 이 펌프들과 소방차들을 이어주는데, 가능한 구간을 고려해보자.
P1<P2<F1<F2일 때 (F1-P1) + (F2-P2) = (F2-P1) + (F1-P2).
P1<F1<P2<F2일 때 (F1-P1) + (F2-P2) < (F2-P1) + (P2-F1).
따라서 구간이 일부분만 겹칠 필요없이, 완전히 포함되거나 독립적이다.

그래서 생각해낸 것이, 구간이 완전히 안에 포함되는 쌍은 바깥쪽 쌍보다 위상이 더 높다고 한다면, 같은 위상 상에서는 완전히 독립적인 구간들 밖에 없어서, 선형 시간에 서로 다른 인접한 원소들을 잘 짝지어서 그 쌍의 합들이 최소화할 수 있게 된다.

위상을 numbering하는 방법은, 펌프들의 위치와 소방차들의 위치를 다 모아놓고 위치순으로 정렬한 다음에, 연속해서 펌프나 소방차가 나온다면, 각각의 경우에 대해 위상의 증감을 반대로 누적해주면 된다.

각 위상마다 애들을 위치순으로 보면 P로 시작해서 F와 P가 번갈아 등장하다가 P로 끝날수도 있고, F로 끝날 수도 있다. (F로 시작하는 건 P로 시작하는 것과 똑같이 처리하면 되므로 일단은 생략)
만약 P로 시작해서 F로 끝나면 그냥 처음부터 보면서 (i+1)번째와 i번째를 짝 지어주는 게 최선이다. 왜냐하면 가능한 짝은 다 지어야하므로.
만약 P로 시작해서 P로 끝난다면 중간에 빈 원소가 하나 생기게 되므로 기존의 인접한 짝들을 지은 것에다가, 끝에서부터 엇갈리게 보면서 새로운 쌍을 이어주고, 기존의 쌍을 없애줄 수 있다. 그 작업을 매번 할 때마다 부분해를 갱신해주면 된다. 그림으로 표현하면 아래와 같다.

따라서 전체적으로 정렬을 사용한다면 O( (N+M) log (N+M) )에 풀 수 있고, 위상에 따라 카운팅 소트하듯이 하면 O(N+M)에 해결할 수 있다.

2 comments:

  1. 위상이 높고 낮음은 어떻게 알 수 있나요? 위상정렬과 관련된 내용인가요?

    ReplyDelete
  2. 덕분에 해결했습니다

    #include
    using namespace std;
    typedef long long ll;
    int main()
    {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int N,M;
    cin>>N>>M;
    vectorP(N),F(M);
    bitset<200001>C;
    vector::iterator pi=P.begin(),fi=F.begin();
    for(auto&I:P)cin>>I;
    for(auto&I:F)cin>>I;
    int W=0;
    while(pi!=P.end()||fi!=F.end())
    {
    if(fi!=F.end()&&pi!=P.end()&&*fi==*pi){C[W++]=1,W++,fi++,pi++;}
    while(fi!=F.end()&&(pi==P.end()||*fi<*pi))C[W++]=1,fi++;
    while(pi!=P.end()&&(fi==F.end()||*pi<*fi))W++,pi++;
    }
    int tpl=0,FS=0,PS=0;
    list >Tl;
    Tl.push_back({});
    list >::iterator IL=Tl.begin();
    pi=P.begin(),fi=F.begin();
    for(int i=0;i::iterator ivE=--I.end();
    for(vector::iterator iv=I.begin();iv!=ivE;)
    {
    tt=D[D[0]]+abs(*(iv)+*(++iv));
    D[++D[0]]=tt;
    iv++;
    }
    int minn=tt;tt=0;
    for(vector::iterator iv=ivE;iv!=I.begin();)
    {
    tt+=abs(*(iv)+*(--iv));
    if(tt+D[--D[0]]::iterator iv=I.begin();iv!=I.end();)
    {
    tot+=abs(*(iv)+*(++iv));
    iv++;
    }
    }
    }cout<<tot;
    }

    ReplyDelete