[C++] 백준 1450 - 냅색문제

https://www.acmicpc.net/problem/1450

1450번: 냅색문제

<알고리즘 분류> 

 - 이분 탐색(Binary Search) 

 - 깊이 우선 탐색(Depth First Search) 

<풀이> 

  1. 30개의 물건이 있고, 이를 선택하는 경우의 수를 모두 더하는 최대 경우의 수는

이다. 따라서 O(2^N)의 시간복잡도를 가지므로 제한시간 1초인 문제에서 시간초과가 발생한다! 

결국 이것을 줄일 수 있는 방법은 

1. 물건들을 절반으로 분리한다.(part1 집합과 part2 집합으로 분리) 

2. 각각의 part에서 만들 수 있는 물건의 무게 값을 push_back 해준다. (이때의 최대 시간복잡도는 O(2^(N/2))이다.) 

3. part1의 집합들을 순회하며(O(N/2)), C-part1[i]를 만족하는 값을 sort된 part2 집합에서 upper_bound(이분탐색+최고인덱스 찾기 알고리즘(O(log(N/2)))을 사용한다. 

결국 이 문제의 시간복잡도는  O(2^(N/2)log2^(N/2)) = O(N*2^(N/2)) 이다. 

 

위의 설명은 다소 비약이 있으니, 예를 들어 설명해 보자. 

<코드>

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <numeric>


using namespace std;
long long N, C; // 물건개수, 최대무게
long long stuff[31];
vector <long long> part1;
vector <long long> part2;
long long cnt = 0;

void dfs(int start, int end, vector <long long>& part, long long sum){
    if(start > end){
        part.push_back(sum);
        return ;
    }
    else { //dfs 2개 : 해당 인덱스(start)를 더해, 말아? 
        dfs(start + 1, end, part, sum); 
        dfs(start + 1, end, part, sum + stuff[start]);
    }
}

int main(){
    cin.tie(NULL);
    cin >> N >> C;
    for (int i=0; i<N; i++){
        cin >> stuff[i];
    }

    dfs(0,N/2, part1, 0);
    dfs(N/2 + 1, N-1, part2, 0);
    sort(part2.begin(), part2.end());
    
    for (int i=0; i < part1.size(); i++){
        cnt += upper_bound(part2.begin(), part2.end(), C - part1[i]) - part2.begin();
    }

    cout << cnt;


}