백준 1450번 냅색문제 - C++ 풀이

---

 

1. 전체 물건을 두 그룹으로 나눈 뒤, 각 그룹에서 가능한 모든 조합을 탐색하여 기록해둔다.
2. A그룹에서 무게 w를 만들 수 있다면, B그룹에서 무게 C-w 이하를 만들 수 있어야 한다.
3. A그룹에서 만들 수 있는 모든 무게에 대해, 이분 탐색을 이용하여 B그룹에서 C-w이하를 만드는 조합의 수를 구한다.

 

1. 전체 물건을 두 그룹으로 나눈 뒤, 각 그룹에서 가능한 모든 조합을 탐색하여 기록해둔다.

 모든 조합의 수는 2^N, N=30이므로 브루트 포스로는 제한시간 내에 통과할 수 없다. 이런 경우 두 그룹으로 쪼개 조합의 가짓수를 줄이는 방법을 사용할 수 있다. 두 그룹 A, B로 나눈 뒤, 각 그룹에서 가능한 모든 조합을 탐색하여 기록해두자. 이 과정의 시간복잡도는 O(2^N/2).

 

2. A그룹에서 무게 w를 만들 수 있다면, B그룹에서 무게 C-w 이하를 만들 수 있어야 한다.

 A그룹에서 무게 w를 만들 수 있다면, 이제 B그룹에서 무게 C-w이하를 만드는 조합의 수를 찾아야 한다.

 

3. A그룹에서 만들 수 있는 모든 무게에 대해, 이분탐색을 이용하여 B그룹에서 C-w이하를 만드는 조합의 수를 구한다.

 각 무게 w에 대해 B그룹에서 C-w이하를 만드는 조합의 수를 구해 더한다. 각 그룹에서 가능한 조합의 수는 O(2^N/2)이므로, 브루트 포스로 B그룹을 탐색할 경우 시간 초과가 나게 된다. B그룹에서 만든 조합의 결과 배열을 정렬한 뒤, 이분탐색을 이용하여 시간을 줄여준다. 전체 시간복잡도는 O(2^(N/2) * log(2^N/2))

반응형

---

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef long long ll;

int N, C;
vector<int> items(30);
vector<int> lCombi, rCombi;

void makeCombi(vector<int>& v, int idx, int x, int end) {
    if (x > C) return;
    if (idx == end) {
        v.push_back(x);
        return;
    }

    makeCombi(v, idx+1, x+items[idx], end);
    makeCombi(v, idx+1, x, end);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> N >> C;
    for (int i=0; i<N; i++) cin >> items[i];

    makeCombi(lCombi, 0, 0, N/2);
    makeCombi(rCombi, N/2, 0, N);
    
    sort(rCombi.begin(), rCombi.end());
    
    ll ans = 0;
    for (auto x: lCombi) {
        ans += upper_bound(rCombi.begin(), rCombi.end(), C-x) - rCombi.begin();
    }
    
    cout << ans;

    return 0;
}