용량 확보( BOJ 9327 )

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

9327번: 용량 확보

 

문제 파악하기

입력되는 e만큼 용량을 확보하기 위해 변환해야 하는 용량의 최소값을 구하는 문제입니다. 용량을 확장하면 기존 용량보다 3배 커지게 됩니다. 이를 용량을 확보하는 관점에서 보자면 확장 시 기존 용량*2 만큼 확보할 수 있습니다. 이 점에 주목하면 문제를 해결할 알고리즘을 설계할 수 있습니다.

 

문제 해결하기

우리는 항상 i번째 세트를 확장시키면 기존 용량*2만큼 추가 공간을 확보할 수 있습니다. 그렇기 때문에 현재까지 확보한 크기를 2로 나눈 값은 우리가 변환한 기존 세트의 용량의 합이 됩니다. 따라서, 우리는 i번째 세트를 확장시키는 경우와 확장시키지 않는 경우를 모두 확인해본 후, 확보해야 하는 e보다 큰 값 중 가장 작은 값을 찾아 2로 나눈 값을 출력하면 됩니다.

 

모든 경우를 확인하는 방법에는 여러 가지 있지만 가장 간단한 방법은 큐와 배열을 사용하는 방법입니다. 큐를 사용해 현재 인덱스와 지금까지 확보한 용량의 크기를 인수로 탐색을 진행하되, 한번 나온 경우인 경우에는 더이상 탐색하지 않는 방법이 있습니다. 이 방법은 구현하기에는 간단하지만, 시간/공간 복잡도 측면에서 비효율적이라는 단점이 있습니다.

 

대신, 1차원 배열을 사용하는 방법이 있습니다. 나올 수 있는 용량을 모두 배열에 저장한 다음, 현재 세트를 확장시켰을 때 나올 수 있는 모든 용량을 구하는 방법이 있습니다. 마치 배낭 문제처럼 배열을 사용하면 이전의 방법보다 시간/공간 복잡도 측면에서 훨씬 효율적으로 해결할 수 있습니다.

 

소스 코드

여기서는 제가 사용한 첫 번째 방법(큐를 사용한 방법) 소스코드를 보여드립니다.

#include <stdio.h>
#include <string.h>
#include <utility>
#include <queue>
#include <vector>
#define GMAX 2000*2*105
#define PAIR pair<int, int>
using namespace std;
 
int T, N, E, t;
vector< int > inp;
 
int idx, val, tot;
bool check[GMAX];
bool dp[105][GMAX];
queue< PAIR > q;
 
int main() {
    scanf("%d", &T);
    while(T--) {
        // init
        tot = 0;
        inp.clear();
        memset(dp, 0, sizeof(dp));
        memset(check, 0, sizeof(check));
        while(!q.empty()) q.pop();
 
        // input
        scanf("%d %d", &N, &E);
        for(int i=0;i<N;i++) {
             scanf("%d", &t);
 
            tot += t*2;
            inp.push_back(t);
        }
 
        // search
        if(tot < E) printf("FULL\n");
        else {
            check[0] = dp[0][0] = 1;
            q.push({0, 0});
            while(!q.empty()) {
                idx = q.front().first;
                val = q.front().second;
                q.pop();
 
                if(idx == N) break;
 
                if(!dp[idx+1][val]) {
                    check[val] = 1;
                    dp[idx+1][val] = 1;
                    q.push({idx+1, val});
                }
 
                if(!dp[idx+1][val+inp[idx]*2]) {
                    check[val+inp[idx]*2] = 1;
                    dp[idx+1][val+inp[idx]*2] = 1;
                    q.push({idx+1, val+inp[idx]*2});
                }
            }
 
            while(!check[E]) E++;
            printf("%d\n", E/2);
        }
    }
}

 

후기

동적 프로그래밍 문제를 연습하고 싶은 사람에게 추천하고 싶은 문제입니다. 개인적으로는 오랜만에 다른 사람의 소스코드를 보고 깜짝 놀란 문제입니다. 아무리 맞춘 문제라도 다른 사람 소스코드를 확인해야 겠다는 생각을 하게 되었습니다.