복구( BOJ 15908 )

문제 : https://www.acmicpc.net/problem/15908

15908번: 복구

 

문제 파악하기

N개의 숫자(사용자 데이터)를 적절하게 지워서 조건에 맞는 사용자 데이터를 만드는 경우의 수 중, 지운 숫자들이 가진 가능성의 최댓값을 가장 작게 만드는 경우를 구하는 문제입니다. 단순히 숫자를 지우기에는 100,000개의 데이터가 너무 많기에 문제를 좀 더 단순화 시킬 필요가 있습니다. 여기서는 총 2가지 단계를 거쳐 문제를 풀어보겠습니다.

 

문제 해결하기

우선, 입력되는 데이터를 보면 총 2가지 종류라는 걸 알 수 있습니다. 첫 번째 N개의 데이터는 사용자 데이터를 의미하며, 두 번째 N개의 데이터는 각각의 데이터가 원래 데이터에 있었을 가능성을 의미합니다. 이 중, 두 번째 데이터인 목록에 있었을 가능성의 값이 정답을 구하는데 가장 큰 영향을 미치게 됩니다. 숫자를 어떻게 생략하든 상관없지만, 생략된 숫자들이 가진 가능성의 최댓값이 작을수록 정답에 가깝기 때문입니다. 그렇기에 우리는 목록에 있었을 가능성에 따라 문제를 분해하여 풀어보겠습니다.

 

결국 문제에서 원하는 건 2가지 입니다. 첫 번째, 현재 데이터를 조각으로 나눌 수 있는가? 두 번째, 나눌 수 있다면 나눈 과정에서 생략된 숫자들이 가진 가능성의 최댓값은? 이 2가지를 한꺼번에 구하기는 쉽지 않습니다. 그렇기에 2가지를 하나씩 단계 별로 나누어보겠습니다. 이 때, 사용할 수 있는 건 바로 이분 탐색을 활용한 파라메트릭 서치 기법입니다. 정답이 될 수 있는 범위는 [ 0 : N ]으로 정해져있으며, 각각의 탐색의 결과(가능/불가능)에 따라 범위를 줄일 수 있기 때문에 해당 기법을 사용하기 적절합니다.

 

우리는 파라메트릭 서치를 통해 한계치를 정한 다음, 한계치보다 작거나 같은 가능성을 가진 숫자만 생략하였을 때 데이터 조각을 나눌 수 있는지 확인하면 됩니다. 만약 현재(한계치) 값으로 데이터 조각을 나눌 수 있다면 현재의 값이 정답일 가능성이 있다는 의미이며, 한계치보다 큰 값은 정답이 될 확률이 없으므로 탐색을 할 필요가 없습니다. 반대로 현재 값으로 데이터 조각을 나눌 수 없다면 더 작은 값에서는 당연히 불가능하기에 탐색할 필요가 없습니다. 이렇게 범위를 절반씩 제거해가면 정답을 O(logN)의 시간 만에 구할 수 있습니다.

 

문제는 한계치에 따라 데이터 조각을 나눌 수 있는지 확인하는 작업입니다. 단순히 모든 경우의 수를 파악하기에는 N의 값이 최대 100,000이라 너무 큽니다. 그렇기에 단순히 브루트포스를 진행하기 보다는 각각의 숫자를 기준으로 생략 가능 여부에 따른 경우의 수를 생각해볼 필요가 있습니다. 우선, dp 배열을 다음과 같이 선언해봅시다.

 

dp[ i ] = (i ~ N)까지의 숫자를 적절하게 생략해서 데이터 조각으로 나눌 수 있는지 여부

 

dp 배열을 0 / 1 중 하나의 값을 가지며, dp[1]의 값에 따라 현재 한계치로 데이터 조각을 나눌 수 있는지 확인할 수 있습니다. 이렇게 배열을 선언한 다음에는 dp[ i ]가 확인해야 하는 값을 경우에 따라 생각해보아야 합니다. 여기서 나올 수 있는 경우란 한계치에 따라 현재 숫자(inp[i])를 생략 가능 여부를 의미합니다. 그럼 각각의 경우에 따라 생각해봅시다.

 

(1) 현재 숫자를 생략할 수 있는 경우

이 경우에는 dp[i+1]의 값에 따라 달라집니다. 만약, dp[i+1]의 값이 1이라면 현재 숫자를 생략하여 (i ~ N)까지의 모든 숫자를 데이터 조각으로 만들 수 있습니다. 그렇기에 이 경우에는 dp[i] = 1의 값을 가지게 됩니다. 하지만, 만약 dp[i+1]의 값이 거짓이라면 아래 알고리즘을 통해 값을 확인해야 합니다.

 

(2) 현재 숫자를 생략할 수 없는 경우

숫자를 생략할 수 없는 경우, 혹은 현재 숫자를 생략했을 때 dp[i]의 값이 거짓(0)이 나오는 경우에는 현재 숫자를 사용해서 데이터 조각을 만들어야 합니다. 여기서 중요한 점은 데이터 조각을 만드는 경우의 수는 어마어마하게 많을 수 있다는 점입니다. 그렇기에 좀 더 포괄적인 시선에서 문제를 바라봐야 합니다. 우선, 현재 숫자를 가지고 만들 수 있는 데이터 조각의 범위를 생각해봅시다. 데이터 조각의 범위란 현재 숫자로 만들 수 있는 데이터 조각의 크기의 최솟값과 최댓값을 의미합니다. 우선 데이터 조각을 작게 만들어봅시다. 데이터 조각을 가장 작게 만들기 위해서는 (현재 숫자의 개수-1)개 만큼 다음에 나오는 모든 숫자를 사용해야 합니다. 그럼 이번에는 데이터 조각을 가장 크게 만들어봅시다. 가장 크게 만들기 위해서는 최대한 생략할 수 있는 숫자들을 모두 생략하면 됩니다. 이는 곧 다음에 나오는 숫자 중 생략할 수 없는 숫자를 (현재 숫자의 개수-1)개 만큼 사용한다는 걸 의미합니다. 이렇게 범위를 구했다면 나머지 일은 간단합니다. 범위 내에 dp[k] 값 중 하나라도 참(1)인 값이 있는지 살펴보면 됩니다. 만약 참인 값이 있다면 우리는 (i ~ k-1)의 값 중 적절하게 생략해서 데이터 조각을 만들면 되며, 나머지 데이터 조각은 dp[k]을 통해 (k ~ N)으로 데이터 조각들을 만들 수 있음이 보장되기에 결국 (i ~ N)으로 데이터 조각들을 만들 수 있음이 보장됩니다.

 

이렇게 2가지 경우에 대해 값을 처리하여 dp[N]에서 dp[1]까지 역순으로 구한 다음, dp[1]의 값을 반환하면 현재의 한계치로 데이터들을 나눌 수 있는지 알 수 있습니다. 이렇게 크게 2개의 단계를 거쳐 탐색을 진행하면 우리가 원하는 결괏값을 얻을 수 있습니다.

 

소스코드

#include <stdio.h>
#include <string.h>
#include <utility>
#include <algorithm>
#define NMAX 100010
#define PAIR pair<int, int>
using namespace std;
 
int N;
PAIR inp[NMAX];
 
int l, r, mid, ret;
int dp[NMAX], cnt[NMAX], check[NMAX];
 
int sz;
int dpCnt[1<<18];
 
void update(int idx) {
    dpCnt[idx] = 1;
    idx /= 2;
 
    while(idx>0) {
        dpCnt[idx] = dpCnt[idx*2] | dpCnt[idx*2+1];
        idx /= 2;
    }
}
 
int search(int l, int r) {
    int ret = 0;
 
    while(l<=r) {
        if(l%2==1) ret |= dpCnt[l++];
        if(r%2==0) ret |= dpCnt[r--];
 
        l /= 2; r /= 2;
    }
 
    return ret;
}
 
bool sv(int val) {
    int ll, rr;
 
    memset(dp, 0, sizeof(dp));
    memset(dpCnt, 0, sizeof(dpCnt));
 
    for(int i=1;i<=N+1;i++) {
        if(inp[i].second > val) {
            cnt[i] = cnt[i-1] + 1;
            check[cnt[i]] = i;
        }
        else cnt[i] = cnt[i-1];
    }
 
    dp[N+1] = 1;
    update(sz + (N+1));
    for(int i=N;i>=1;i--) {
        if(dp[i+1] and inp[i].second <= val) dp[i] = 1;
        else {
            // 불가능한 경우
            if(i+inp[i].first - 1 > N) continue;
 
            // ll: 숫자를 1개도 지우지 않은 경우
            ll = i + inp[i].first;
 
            // rr: 숫자를 최대로 지운 경우 >> cnt[ (cnt[i]+inp[i].first) ] 찾기
            if(cnt[i]+inp[i].first > cnt[N]) rr = N+1;
            else rr = check[cnt[i] + inp[i].first];
 
            // (ll ~ rr) 사이에 true가 있는지 확인
            if(ll <= rr) dp[i] = search(ll+sz, rr+sz);
        }
 
        if(dp[i]) update(i+sz);
    }
 
    return dp[1];
}
 
int main() {
    // 입력
    scanf("%d", &N);
    for(int i=1;i<=N;i++) scanf("%d", &inp[i].first);
    for(int i=1;i<=N;i++) {
        scanf("%d", &inp[i].second);
        r = max(r, inp[i].second);
    }
 
    for(sz=1;sz<N;sz*=2);
 
    // 파라메트릭 서치
    ret = NMAX;
    while(l<=r) {
        mid = (l+r)/2;
 
        if(!sv(mid)) l = mid+1;
        else {
            ret = min(ret, mid);
            r = mid-1;
        }
    }
 
    // 출력
    printf("%d", ret);
 
}
 
/*
4
2 1 1 2
3 1 2 2
*/

후기

한계치에 따라 데이터 조각을 나눌 수 있는지 확인하는데 몹시 어려웠던 문제였습니다. 이 문제는 shake! 2018에 출제되었던 문제로 공식 해설도 있으니 참고하셔도 좋을 듯 합니다. 동적 프로그래밍에 자신 있는 사람에게 추천하고 싶은 문제입니다.