KOI 2011 지역본선 책장

Problem

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

Summary

N 개의 책이 주어진다.

각 책 마다 너비 W 와 높이 H 가 주어지고, 주어진 순서대로 책장에 꽂으려 한다.

모든 책을 꽂기 위한 책장의 너비와 높이중 최대값을 최소로 하려고 할 때, 그 최소값은 얼마일까?

Solution

너비와 높이 중 최대값을 최소로 하는 문제이다.

모든 책을 꽂아야 하는 책장의 특성상 너비가 증가함에 따라 높이가 단조감소하고, 너비가 줄어들면 높이가 단조증가하게 된다.

따라서 책장의 너비(폭) 을 고정시키고, 그 때의 최소 높이를 구한 다음 그 높이를 기준으로 책장의 너비를 늘릴지 줄일지 결정할 수 있고 따라서 이 문제는 파라메트릭 서치로 접근 가능하다.

그렇다면 책장의 너비를 고정 시켰을 때 모든 책을 꽂기 위한 최소 높이를 구하는 방법에 대해 알아보자.

1.   Solution

책을 꽂는 순서가 정해져 있기 때문에 마지막 층에 꽂을 책을 결정하고 나면, 맨 위에 책들을 제외한 책들에 대해 최소 높이를 구하면 된다. 따라서 재귀적으로 문제 크기를 단계적으로 줄여나갈 수 있고, 동적계획법으로 문제를 해결 할 수 있다.

와 같이 표현 할 수 있고, 각 i 에 대해 모든 후보 j 에 대해 검사를 하여 정답을 구할 수 있다.

2.   Solution

위의 점화식을 다시 한번 살펴 보자.

고정된 i 에 대해 편의상 max(h[j...i]) = H[j] 라고 표현하면

D[i] =max { D[j-1] + H[j] } 로 나타난다. 

여기서 max 함수 안에 있는 각 항을 따로 살펴보면

D[j-1]: j 가 증가 함에 따라 단조 증가하는 그래프를 그린다.

H[j]: j가 증가 함에 따라 단조 감소하는 그래프를 그린다. (j 가 감소함에 따라 증가한다.)

D와 H의 개형을 대략적으로 나타내면 위의 그림과 같다. 

이러한 상황에서 D와 H를 더한 값을 최소로 하는 j를 찾는것이 이 문제의 핵심이다.

그래프의 개형을 통해 아래의 Lemma를 얻을 수 있다.

lemma 1: 고정된 i 에 대해, H[j]이 같은 한 가장 작은 j를 선택하는 것이 유리하다. 즉 H[j]가 감소하는 j에 대해서만 고려해도 충분하다.

따라서 i 가 고정되어 있을때에는 H[j]가 감소하는 j 리스트를 가지고 있어, 이 j 에 대해서만 식을 계산해도 충분하다.

그렇다면 i 가 증가할 때 그래프의 개형을 살펴보자

위와같이 i+1 번째 책이 이전 책보다 높이가 큰 경우와 작은경우 두가지 경우가 나올 수 있다.

또 세로축이 오른쪽으로 이동한 이유는 문제 조건 상 (w[j] + ... + w[i] <= L) 을 만족해야 되기 때문에 i 가 증가함에 따라 가능한 j의 범위는 점점 감소하기 때문이다.

i 일때 고려해야되는 j 의 후보를 list[i] , i + 1 일때 고려해야되는 j 의 후보를 list[i+1] 이라 하면

list[i+1] 은 list[i]의 앞에서 몇개의 원소가 삭제되고, list[i]의 뒤에서 몇개의 원소가 삭제되거나 추가된 형태가 된다.

그리고 여기서 삭제된 j들은 이후 i 의 값과 상관없이 고려해야할 대상에서 아에 제거된다. (한번 높아진 H[j] 값이 다시 감소 하지 않기 때문)

이를 정리하면 아래와 같은 lemma 를 얻는다.

lemma 2: i 가 증가함에 따라 고려해야되는 j 의 후보는 앞 / 뒤에서 추가 혹은 삭제되며 한번 후보에서 빠진 j 는 i 에 상관없이 다시 고려될 필요 없다.

따라서 i 가 증가하는 순서로 D[i] 값을 계산할 때 고려해야 하는 j 의 후보군들을 deque로 관리하면 원소가 앞, 뒤에서 추가 혹은 제거되는 상황을 효과적으로 처리 할 수 있다.

하지만 최악의 경우 각 i 에대해 고려해야 할 j 의 후보군이 n 에 비례 할 수도 있기 때문에 매번 list 의 모든 후보에 대해 계산하면 O(N^2) 이 된다.

따라서 매번 후보에 대한 계산을 하지 않고 리스트에 삽입되는 순간 D[j-1] + H[j] 값을 계산하고 이 값을 우선순위큐에 넣어둔다. 그런 다음 D[i] 를 계산 할 때 우선순위 큐에서 가장 작은 원소를 뽑아 D[i] 값을 계산한다.

여기서 주의할 접은 리스트에서 제거되는 원소에 대해서는 그 값을 고려하면 안되기 때문에 큐에서 뽑은 뒤 이 값이 현재 deque 안에 있는 j 에 의해 계산된 값인지 확인하는 과정이 필요하다.

lemma2 에 따라 각 원소는 최대 한번 리스트에 삽입 / 삭제 되기 때문에 우선순위 큐에 삽입되는 원소 또한 N 에 비례하며 따라서 D[1] ... D[N] 까지의 모든 값 계산을 N log N 시간만에 해결 할 수 있다.

3.   Solution

이 문제를 O(N) 으로 해결하기 위해서는 후보 j 에 대한 값을 저장하기 위해 사용한 우선순위 큐 대신, 값이 증가하는 데큐 하나와 값이 감소 하는 데큐 2개를 사용하면 된다. 하지만 기본적으로 j후보가 앞/뒤에서 dynamic 하게 추가 삭제되기 때문에 데큐안의 원소를 우리가 원하는 범위 안의 값으로 잘 관리해주기 상당히 까다로울 것으로 예상된다.

p.s) 위의 O(N log N) 솔루션으로도 충분히 제한시간 안으로 답을 구해낼 수 있다.

Implementation

아래 코드는 두번째 방법인 O(N log N) 으로 구현되어 있습니다.

우선순위 큐 안의 원소가 현재 deque 안의 원소에서 계산된 값인지 확인하기 위해 valid 라는 배열을 두어 큐에서 뽑을 때 매번 확인하는 과정이 포함되어 있습니다.

#include <stdio.h>

#include <deque>

#include <queue>

#define maxf(a,b) ((a)>(b)?(a):(b))

#define minf(a,b) ((a)<(b)?(a):(b))

using namespace std;

 

struct seq {

    bool operator < (const seq i)  const{ return dp > i.dp; }

    seq() { i = H = dp = 0; }

    seq(int _i,int _H,int _dp) { i = _i; H = _H; dp = _dp; }

    int i,H,dp;

} last;

 

priority_queue<seq> table;

deque<seq> list;

int N, D[100010], valid[100010], S[100010];

int T[100010][2];

 

int f(int M) {

    int fJ, nowH, i;

 

    //초기화

    fJ = 1;

    for(i=1;i<=N;i++){ D[i] = 0; S[i]=0; valid[i] = -1; }

    for(i=1;i<=N;i++){ S[i] = T[i][0]; S[i] += S[i-1]; }

    while(!list.empty()) list.pop_back(); while(!table.empty()) table.pop();

 

    list.push_back(seq(1,T[1][1],D[1-1]+T[1][1]));

    table.push(seq(1,T[1][1],D[1-1]+T[1][1]));

    valid[1] = D[1-1] + T[1][1];

    D[1] = T[1][1];

     

    for(i=2;i<=N;i++) {

        // list들중 앞에서 pop되는 것들

        while( S[i] - S[fJ-1] > M ) fJ ++;

        while( !list.empty() && list.front().i < fJ ) {

            last=list.front(); list.pop_front();

            valid[last.i] = -1;

        }

        if( list.empty() || list.front().i != fJ ) {

            last.i = fJ; last.dp = D[last.i-1] + last.H;

            list.push_front(last);

            table.push(last);

            valid[last.i] = last.dp;

        }

        // 현재 높이 update

        nowH = T[i][1];

        last = seq(i,nowH,D[i-1]+nowH);

        while( !list.empty() && list.back().H < nowH ) {

            last = list.back(); list.pop_back();

            valid[last.i] = -1;

        }

        last.H = nowH; last.dp = D[last.i-1] + last.H;

        list.push_back(last);

        table.push(last);

        valid[last.i] = last.dp;

         

        // dp값 구하기

        while( valid[table.top().i] != table.top().dp ) table.pop();

        D[i] = table.top().dp;

    }

    return D[N];

}

 

int main() {

    int l,r,m,ans=1e9,v,i; l = 0;

    scanf("%d",&N);

    for(i=1;i<=N;i++) {

        scanf("%d%d",&T[i][0],&T[i][1]);

        l = maxf(l,T[i][0]);

    }

    r = 10000 * N;

    while(l<=r) {

        m = (l+r)>>1;

        v = f(m);

        ans = minf( ans , maxf(v,m) );

        if(v>m) l = m + 1;

        else r = m - 1;

    }

    printf("%d",ans);

    return 0;

}