[알고리즘] 백준 1450 냅색문제

📖문제

1450 냅색문제

💡구상

경우의 수 문제이므로 탐색을 진행해야 한다.
1. 완전 탐색? -> N개의 물건이므로 완전 탐색을 진행하면 경우의 수는 2^30 이므로 불가능하다.
2. DP? -> C의 최댓값이 10^9 이므로 DP배열의 인덱스에 넣을 수 없다.

그렇다면 어떻게 해야할까?? 코드와 함께 살펴보자.

🔍코드

#include<bits/stdc++.h> 
using namespace std;
typedef long long ll;
ll n,c;
ll a[31],ret;
vector<int> v,v2;
void go(int here , int _n, vector<int> &v, int sum){
	// 가방 최대 무게 초과하는 경우 
	if(sum>c) return;
	// 탐색이 종료되면 v에 담고 종료 
	if(here > _n){
		v.push_back(sum);
		return;
	}
	// 가방에 넣는 경우 
	go(here+1, _n, v, sum+a[here]);
	// 가방에 넣지 않는 경우 
	go(here+1, _n, v, sum);
	
	return;
} 
int main(){
	cin>>n>>c;
	for(int i=0; i<n; i++){
		cin>>a[i];
	}
	// 0~n/2 탐색 
	go(0,n/2-1,v,0);
	// n/2 ~ n-1 탐색 
	go(n/2,n-1,v2,0);
	// sorting
	sort(v.begin(),v.end());
	sort(v2.begin(),v2.end());
	// 경우의 수 합치기 
	for(int b : v){
		if(c-b >=0) ret += ((int)(upper_bound(v2.begin(),v2.end(),c-b)-v2.begin()));
	}
	cout<<ret<<"\n";
	return 0;
}

먼저 이 코드를 이해하기 위해서는 Meet in the middle 알고리즘을 이해해야 한다.

Meet in the middle?

N개를 완전탐색할때, N이 너무 큰 경우 N을 반으로 쪼개서 N/2 씩 완전탐색하는 알고리즘이다.

{1,2,3,4,5,6}을 탐색하고 C = 15인 경우를 생각해보자.

{1,2,3,4,5,6}을 {1,2,3},{4,5,6}으로 나누어 각각 v1,v2벡터에 탐색하며 얻은 합을 저장한다.

이제 나눈 두 벡터를 적절히 조합해야 한다.

만약에 v1에서 0을 골랐을때, v2에는 어떤 경우의 수가 가능할까?
가방의 최대 무게가 15이므로 v2와 합해서 15이하가 된다면 가능한 경우의 수이다.

즉, v1이 0인 경우, 가능한 경우의 수 8
v1이 1인 경우 v2에선 14(15-1) 까지 고를 수 있으므로 가능한 경우의 수 7
v1이 2인 경우 v2에선 13(15-2) 까지 고를 수 있으므로 가능한 경우의 수 7 ...
이렇게 v1을 탐색하면서 자신의 case(b)에서 가능한 v2의 case(c-b 이하)를 더해간다면 우리가 원하는 해답이 나올 것이다.

upper_bound()

오름차순 정렬된 배열에서 찾으려는 key 값을 초과하는 숫자가 배열 몇번째 처음 등장하는지 찾기 위한 함수이다.

예시

#include <iostream>
#include <algorithm>
using namespace std;

int main() {

	vector<int> arr = { 1,2,3,4,5,6 };
	cout << "upper_bound(3) : " << upper_bound(arr.begin(), arr.end(), 3) - arr.begin();

    // 결과 -> upper_bound(3) : 3
	return 0;
}

이 문제에선 upper_bound를 통해서 가능한 경우의 수를 빠르게 구할 수 있다!