[도전 4일차] 2488 줄다리기

문제 : BOJ 2488 줄다리기

문제 링크

줄다리기

2009 KOI 전국본선 고등부 2번 

 

사용 알고리즘 : 라인 스위핑

 

문제 분석 :

두 무리의 사람들이 있다. 각각의 무리를 A,B라 할 때 A 무리와 B 무리를 각각 3 모둠으로 분단한다.

사람들 a1,a2,a3,a4,a5 ,b1,b2,b3 가 있다고 하면 임의로

a1,a2 || a3,a4 || a5 

b1 || b2 || b3

와 같이 사람들을 분단할 수 있다.

각각의 모둠을 순서대로 1,2,3이라 하고 A무리와 B 무리를 구별하여 A1,A2,A3,B1,B2,B3 모둠이라 하자.

이때 모든 사람들의 몸무게가 주어진다. 분단 시 규칙은 모든 i에 대하여 A i 모둠과 B i 모둠의 몸무게 차이는 50이하가 되어야 한다. 중요한 점은 모든 사람의 몸무게는 20 이상 100 이하라는 점이다.

우리가 구해야 하는 것은 "세 모둠 각각의 몸무게 차이의 최대값"을 최소로 하는 줄다리기 모둠 분단이다.

 

풀이: 

*꽤 복잡한 과정이기 때문에 코드를 IDE에 넣고 설명과 병행하여 공부하시는 것을 추천 드린다.

그 후 반드시 코드를 스스로 처음부터 다시 짜는 과정을 거쳐야 온전히 자기 것으로 만들 수 있다.

Key point 1 :  A1 구간을 임의로 정해보자. 몸무게 합을 x라 할 때 B1 몸무게 합의 범위는 x-50 ~ x+50 이다.

B에 속한 사람들을 살펴볼 때 B1 몸무게의 합이 x-50 이상이 되는, 즉 lower_bound 인 사람이 있을 것이다. 편의상 몸무게의 합을 x-50이라 가정하자. 이때 각 사람의 몸무게는 20 이상이므로 나올 수 있는 경우의 수는 x-50, x-30, x-10, x+10, x+30, x+50 많아야 6가지 이다. 

 

A1이 변함에 따라 A1-B1이 같은 분단점 쌍이 2가지 이상 나왔다고 생각해보자.

k 를 A1-B1+50 (차이는 -50부터 +50까지 가능하므로 0~100으로 index 설정)이라 하자.

만약 k가 이전에 1번 나왔다고 하자. 같은 차이를 가진다는 뜻은  A1구간과 B1구간에 동일한 합을 가지는 숫자들이 각각 추가됐다는 뜻인데 , 그 숫자들을 2번째 구간에 밀어넣어도 똑같은 결과를 가지기 때문에 가장 처음 계산한 것으로 해도 문제 없다. 즉, 1번째 구간의 가능한 차이 0~100, 즉 최대 100가지 경우에 대해서 분단점 쌍을 구할 수 있다.

 

1번째 구간과 3번째 구간에 대해 구한 분단점 쌍을 바탕으로 100*100의 시간 복잡도로, 구한 분단점이 적합한지 확인함과 동시에 구하는 값을 최소로 하는 분단점을 갱신할 수 있다.

 

시간복잡도에서 지배적인 부분은 1번째 구간에서 가능한 분단점, 3번째 구간에서 가능한 분단점을 구하는 과정이다.

내가 본 풀이에서는 시간복잡도가 O(n)이라 설명하였는데, 나는 납득이 잘 가지 않았다.

코드를 보면 알겠지만 

for(int i=1, t=1;i<=n-2;i++){

while(t​<m-2&& B[t]<A[i]-50) t++; //B1이  가능한 구간의 왼쪽 끝점  

...

}

이 부분은 B 구간합 배열에서 A[i] -50 에 대한 lower_bound 비슷한 걸 구하는 과정이다. std::lower_bound를 쓰면 실제로 시간복잡도를 줄일 수 있다. 그런데 그렇게 구하지 않아도 실제로는 거의 비슷한 시간에 동작한다. 

만약 A에 속한 사람들의 몸무게가 모두 100, 그리고 B에 속한 사람들의 몸무게가 모두 20이라 가정하자. 

그러면 i가 1 증가할 때 마다 t++을 해주는 횟수는 5씩 증가할 것이다. 간단하게 생각하면 sum(min(m,5i)) 정도로 생각할 수 있다. n,m이 30000이라 할 때  i>6000 인 순간 더하는 값은 m=30000으로 고정된다. 아니 엥 잠깐만 그렇게 되면

sum(min(m,5i) ) = sum(5i ) (1<=i<=6000) + sum(m) (6000<i<=30000) 이 되고 이는 대략적으로 계산했을 때 80억 정도다. TLE 컷이다.. 그렇다 채점데이터가 약한 것이다. 

 

난 이것이 O(n) 풀이라는 것에 동의하지 못한다. 그렇다 아래 코드는 단지 채점 데이터가 약했던 탓에 빠르게 통과할 수 있었다. 그렇다면 어떻게 시간 복잡도를 줄일 수 있는가? 

 

그 방법은 바로

t= lower_bound(b+1,b+m+1,a[i]-50)-b;
if(t>m-2) t=m-2;

코드를 이용하므로써 시간 log m으로 줄일 수 있다.

 

마찬가지로 3번째 구간을 구할때도 b2[m-i+1] = b[m] - b[i] 배열을 만듬으로써

1번째 구간과 동일하게 lower_bound로 처리할 수 있다. 

그렇게 되면 O(n log2(n) ) 풀이가 된다.

아래 코드를 더 최적화 해보시기 바란다. 백준에서는 O(log2n)으로 했을 때 B2 배열을 만드는 시간 때문에 

4ms 에서 8ms로 시간이 증가했다.

코드

//2020.4.1
//wade3han님의 코드를 보고 공부. 
//pentagon@sasa.hs.kr 
#include<bits/stdc++.h>
#define ll long long
#define vsort(v) sort(v.begin(),v.end());
const int INF = 1e9;
using namespace std;
int n,m,A[30010],B[30010];
pair<int,int> c1[101],c2[101];
int ans=INF,c,a1,a2,b1,b2;
int main(){
    scanf("%d%d",&n,&m);
    // 1. 구간합 배열 생성  
    for(int i=1;i<=n;i++)
        scanf("%d",A+i),A[i]+=A[i-1];
    for(int i=1;i<=m;i++)
        scanf("%d",B+i),B[i]+=B[i-1];
        
    //c1 : 1번째 구간의 끝 , c2 : 2번째 구간의 끝 , pair 순서대로 A,B 
    // 2. 1번째 구간의 크기 정하기
    for(int i=1, t=1;i<=n-2;i++){
        while(t<m-2 && B[t]<A[i]-50) t++; //B1이  가능한 구간의 왼쪽 끝점  
        for(int j=t,k;j<=m-2 && abs(A[i]-B[j])<=50;j++){
            k = A[i] - B[j] + 50; //차이는 -50부터 +50까지 가능하므로 0~100으로 index 설정
            if(!c1[k].first) c1[k] = make_pair(i,j);   
            //만약 k가 이전에 1번 더 나왔다고 하자. 같은 차이를 보인다는 뜻은 
            //A1구간과 B1구간에 동일한 합을 가지는 숫자들이 각각 추가됐다는 뜻인데 
            // 이를 2번째 구간에 밀어넣어도 똑같은 결과를 가지기 때문에 
 // 가장 처음 계산한 분단점으로 해도 문제 없다.
        }
    } 
    // 3. 3번째 구간의 크기 정하기, 이번엔 끝에서부터 시작한다.(2번째 구간의 크기는 자동 결정) 
    for(int i=n-1,t=m-1;i>=2;i--){
        while(t>2 && (B[m]-B[t])<(A[n]-A[i])-50) t--; //B2가 가능한 구간의 오른쪽 끝점. 
        for(int j=t,k;j>=2 && abs( (A[n]-A[i]) - (B[m]-B[j]) ) <= 50;j--){
            k= (A[n]-A[i]) - (B[m]-B[j]) + 50;
            if(!c2[k].first) c2[k] = make_pair(i,j);
        }
    } 
    // 4. 모든 차이에 대하여 그 index가 적합한지 확인하고, 정답을 갱신한다. 
    //이때 i 는 A1 - B1 +50  , j는 A3 - B3  +50 이므로 A2 - B2  = A[n] -B[m] -(i-50) -(j-50) 이다.
    
    for(int i=0;i<=100;i++){
        for(int j=0;j<=100;j++){
            if(c1[i].first && c2[j].first && c1[i].first < c2[j].first && c1[i].second < c2[j].second){
                c=max({abs(i-50),abs(A[n]-B[m]-(i-50)-(j-50)),abs(j-50)});
                if(c<ans){
                    ans=c;
                    a1=c1[i].first;
                    a2=c2[j].first;
                    b1=c1[i].second;
                    b2=c2[j].second;
                }
            }
        }
    } 
    if(a1)
        printf("%d %d %d\n%d %d %d",a1,a2-a1,n-a2,b1,b2-b1,m-b2);
    else
        printf("-1");
}

* 이분이 원 저작자인지는 확실치 않지만 내가 참고한 코드의 작성자는 wade3han님이다.

 

*무한 미루기 선사 덕분에, 늦은 시간에 문제 분석을 시작했다. 문제 이해를 완료하고 1시간 정도 도전 후 풀이를 실컷 찾았다. 놀랍게도 블로그에 풀이를 올린 사람이 아무도 없어 몹시 고생했다. 그러다가 기적 같이 KOI 고등부 풀이집을 찾게 되었고 그곳에서 풀이를 얻어 공부했다. 그 후 다시 백준에서 wade3han의 코드를 보고 코드를 최적화했다.