보석 모으기( BOJ 1480 )

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

1480번: 보석 모으기

 

문제 파악하기

N개의 보석을 M개의 가방에 적절하게 넣어서 챙길 수 있는 보석의 최대 개수를 구하는 문제입니다. 각각의 보석은 1~20그램의 무게를 가지며, 가방에는 최대 C그램의 보석을 담을 수 있습니다. 만약 가방이 한 개라면 입력되는 범위 값이 작기 때문에 브루트 포스 알고리즘으로 충분히 해결할 수 있지만, 가방이 최대 10개까지 있을 수 있기 때문에 좀 더 효율적인 방법이 필요합니다.

 

문제 해결하기

떠올릴 수 있는 가장 간단한 방법은 우리에게 필요한 모든 조건을 재귀함수의 매개변수로 설정하는 것입니다. 우리가 탐색을 할 때 필요한 정보를 모두 생각해보면 { 지금 가방에 넣을지 말지 결정할 보석 번호, 지금까지 사용한 가방 개수, 지금까지 가방에 넣은 보석 무게, 지금까지 사용한 보석 현황 } 과 같이 나올 수 있습니다. 이를 재귀함수로 표현한다면 다음과 같이 표현할 수 있습니다.

 

void sv( int idx, int bag, int weight, int check[15]) { }

 

이렇게 재귀함수를 만든 다음에, check 값에 표시된 개수를 세어보면 우리가 원하는 값을 구할 수 있습니다. 다만, 이 재귀함수를 사용하는 알고리즘은 가방의 개수가 적을 때만 가능하며, 지금처럼 최대 10개의 가방을 사용할 수 있는 경우에는 턱없이 오래 걸리는 알고리즘입니다. 하지만, 위의 알고리즘을 적절하게 가공하면 좀 더 빠르게 작동할 수 있게 만들 수 있습니다.

 

보통 재귀함수를 가공한다는 건 재귀함수에서 사용하는 매개변수의 형태를 바꾸거나 줄이는 걸 의미합니다. 우선, 가장 부피를 많이 차지하는 배열부터 없애봅시다. 보통 배열을 없애는 건 힘든 일이지만 다행히 이번 문제처럼 N의 범위가 작으며, N개의 숫자의 사용 여부를 단순히 체크하는 건 변수 1개로 변환할 수 있습니다. check배열을 정수형 변수 check로 바꾸고, 탐색 시 비트마스킹 기법을 도입해봅시다. 그럼 우리의 함수는 총 4개의 정수형 변수를 가진 재귀함수로 바뀌었습니다.

 

void sv(int idx, int bag, int weight, int check) { }

 

이렇게 모든 매개변수가 정수형 변수로 바뀌었고, 모든 변수의 값이 배열의 인덱스로 사용하기 적합하다면 메모이제이션 기법을 활용해서 시간 복잡도를 줄일 수 있습니다. 하지만 아직 매개변수가 많고, sv( )함수가 탐색할 범위가 아직도 많아 2초라는 시간이 부족할 수 있습니다. 따라서, 4개의 매개변수 중 필요없는 매개변수를 제거할 필요가 있습니다. 우선, 가장 앞에 있는 idx 변수를 생각해봅시다. idx 변수가 꼭 필요할까요? idx 변수가 없다면 다른 곳에서 탐색할 수는 없을까요? 옆에 있는 bag 변수는 어떨까요? bag 변수도 꼭 필요할까요? 이렇게 변수마다 꼭 필요한지, 아니면 다른 매개변수를 사용하여 생략할 수 있는지 고민해보면 재귀함수의 매개변수 값을 줄여서 더욱 빠르게 답을 구할 수 있습니다. 물론, 무작정 매개변수를 줄이면 정확한 탐색이 어려워지고 심지어 시간이 더 걸리는 경우도 있습니다. 그렇기에 매개변수를 적절하게 줄여야 합니다.

 

sv( )함수에서 사용한 4개의 변수를 보면, 사실 꼭 필요하지 않은 변수 1개가 보입니다. 첫 번째, idx 변수입니다. idx 변수는 check 변수을 활용하면 꼭 필요하지 않습니다. check에서 이미 이전 가방에서 사용한 모든 보석들을 체크했기에 check 변수에서 0인 보석만 따로 확인해보면 됩니다. 그리고 weight변수를 보면 제거할 수 있습니다. 다만, weight변수를 그대로 사용하면 메모리는 더 커지지만 시간 복잡도는 줄기에 생략 여부는 선택하면 됩니다. 참고로 저는 weight 변수도 생략했습니다. 대신, 각각의 가방에서 넣을 수 있는 모든 경우를 확인하는 방식을 사용했습니다. 이렇게 문제를 해결할 수 있는 상황(재귀함수)를 만든 다음, 적절한 연산 및 처리를 통해 빠르게 작동하도록 가공할 수 있습니다. 자세한 소스코드는 다음과 같습니다.

 

소스코드

#include <stdio.h>
#include <string.h>
#include <vector>
#include <utility>
#include <algorithm>
#define NMAX 15
#define MMAX 15
#define PAIR pair<int, int>
using namespace std;
 
int N, M, C, t;
vector< int > inp;
 
PAIR calc[1<<NMAX];
int dp[MMAX][1<<NMAX];
 
int sv(int bag, int check) {
    if(dp[bag][check] >= 0) return dp[bag][check];
    else if(bag == M) return dp[bag][check] = 0;
    else {
        int ret;
        
        ret = 0;
        for(int select=0;select<(1<<N);select++) {
            if(select & check) continue;
            
            // 가방에 넣을 수 있는 경우
            if(calc[select].first <= C) ret = max( ret, sv(bag+1, check | select)+calc[select].second );
        }
        
        return dp[bag][check] = ret;
    }
}
 
int main() {
    // 입력
    scanf("%d %d %d", &N, &M, &C);
    for(int i=0;i<N;i++) {
        scanf("%d", &t);
        inp.push_back(t);
    }
    
    // 전처리
    // calc[check]: 챙긴 보석이 check일 때, { 총 무게, 보석의 수 }
    for(int check=0;check<(1<<N);check++) {
        for(int c=0;c<N;c++) {
            if(check & (1<<c)) {
                calc[check].first += inp[c];
                calc[check].second++;
            }
        }
    }
    
    // 출력
    memset(dp, -1, sizeof(dp));
    printf("%d", sv(0, 0));
    
}
 
 

후기

입력되는 숫자의 범위가 작아서 단순하게 생각했다가 된통 당한 문제입니다. 제가 설계한 알고리즘은 매개변수를 너무 줄여서 오히려 시간이 오래 걸렸다는 문제가 있어서 다른 사람들 소스코드를 보면서 배울 수 있었습니다. 점화식 혹은 매개변수를 정하는데 재미있던 문제라 동적 프로그래밍을 연습하거나 비트마스킹을 연습하는 사람에게 추천하고 싶은 문제입니다.