BOJ 1450 - 냅색문제

www.acmicpc.net/problem/1450

1450번: 냅색문제

 

 

이 문제는 meat in the middle 이라는 알고리즘을 써서 풀어야 하는 문제이다

(참조) meat in the middle

blog.naver.com/PostView.nhn?blogId=kks227&logNo=221382873753&proxyReferer=https:%2F%2Fwww.google.com%2F 

밋 인 더 미들(Meet in the Middle) (수정: 2018-10-25)

 

이 문제는 무게의 합이 C 이하인 모든 부분집합의 경우의 수를 세야하는 문제로, 

절반씩 나눠서 앞 그룹(first), 뒷 그룹(second) 이렇게 두개의 그룹으로 나눈다

이렇게 나누면서, 시작 인덱스가 끝 인덱스를 초과하는경우, 벡터에 합산 값을 넣는다 (물건들의 무게의 합)

그 후, 두번째 그룹을 오름차순 정렬하고 (upper_bound 를 쓰기 위해서임)

upper_bound 로 첫번째 그룹의 i 번째 무게와 두번째 그룹의 무게를 조합해서 가능 무게 C 를 초과하지 않는 경우를 카운팅해서 답에 추가한다.

 

 

사실 이문제는 다른 사람들의 답을 그냥 봤다. 처음 보는 알고리즘이기도 하고, 어떻게 접근해야될지 감이 전혀 오지 않았기 때문이다.

 

 

- C++

#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
 
ll N, C, answer; // 물건갯수, 가방 최대 용량, 답
ll stuff[31]; // 물건 정보
vector<ll> first, second; // 두 그룹으로 나눠서 반반 탐색
 
void recursion(int s, int e, vector<ll>& vec, ll sum) { // 절반씩 나눠서 두 그룹으로 분배하기 위한 재귀함수
    if (s > e) {
        vec.push_back(sum);
        return;
    }
    
    recursion(s + 1, e, vec, sum);
    recursion(s + 1, e, vec, sum + stuff[s]);
}
 
int main() {
    cin.tie(0); ios_base::sync_with_stdio(0);
    
    cin >> N >> C;
    
    for (int i = 0; i < N; ++i) cin >> stuff[i];
    
    recursion(0, N / 2, first, 0); // 절반씩 나눠서 탐색
    recursion(N / 2 + 1, N - 1, second, 0);
    
    sort(second.begin(), second.end()); // upper_bound 는 이진탐색 기반이므로 이미 정렬되어 있는 상태여야함.
    
    for (int i = 0; i < first.size(); ++i) {
        answer += upper_bound(second.begin(), second.end(), C - first[i]) - second.begin(); // 두번째 그룹의 시작과 끝에서 C - first[i] 를 초과하는 값 - 두번째 그룹의 
    }
    
    cout << answer;
    
    return 0;
}