백준 1450 - 냅색 문제(C++)

문제 링크입니다. https://www.acmicpc.net/problem/1450

1450번: 냅색문제

'중간에서 만나기' 를 사용하는 문제입니다.

가방에 물건을 C이하만큼 넣을 수 있습니다.

하나의 물건에서 할 수 있는 경우는 선택O / 선택X인 2가지입니다. 

물건이 총 30개까지 주어지니, 전체의 경우는 2^30입니다. -> 시간초과가 생깁니다.

따라서, 문제를 풀기 위해선 '중간에서 만나기'를 사용해야합니다.

 

중간에서 만나기란, 전체 경우를 2가지로 나눠서 생각하는 것입니다.

이 문제에서는 15개씩 물건을 나눠 경우를 확인하는 것입니다.

그렇게 되면, 2^15을 2번만 하면 되니, 전체를 살피는 것보다 훨씬 빠릅니다.

 

가방의 무게를 전부 채우는 것이 아닌, C 이하만큼만 채우면 됩니다. 

그렇다면 2개의 범위를 통해 얻은 범위를 통해, A or B범위 중에 한 값을 고정한 뒤, 다른 범위에서 조건을 만족하는 갯수를 전부 구하면 됩니다.

 

예를 들어, 10이하는 무게를 채울 때,

(1, 1, 2, 2, 3, 5, 7, 7, 9, 10)  /  (1,1,1,1,2,3,3,4,5,6,7,7,8,10) 의 값이 구해졌다고 해보겠습니다.

앞의 값을 고정시킨뒤, 뒤에 갚을 더해 10보다 큰 수나 나올 때를 찾습니다. 해당 위치 전까지가 넣을 수 있는 경우의 수입니다.

->이는 upper_bound를 통해 쉽게 구할 수 있습니다.

 

따라서,

1. 두 가지 범위로 나눠서 경우의 수를 구한다.

2. 한 범위는 고정, 다른 범위는 오름차순 정렬을 한다.

3. 고정 시킨 범위를 통해, 몇가지가 가능한지를 찾는다.

 

 

자세한 것은 코드를 참고해주세요

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstdio>
#include <string>
#include <deque>
#include <stack>
#include <map>

using namespace std;

int N, C;
int weight[31];
map<long long, int> Sum;
vector<long long> sum1, sum2;
long long ans;

void right_sum(int mid, long long sum){
    if(mid == N){
        sum1.push_back(sum);
        return;
    }
    right_sum(mid+1, sum+weight[mid]);
    right_sum(mid+1, sum);
}

void left_sum(int st, long long sum){
    if(st == N/2){
        sum2.push_back(sum);
        return;
    }
    left_sum(st+1, sum+weight[st]);
    left_sum(st+1, sum);
}

void solve() {
	right_sum(N/2, 0); // 시작위치, 합
	left_sum(0, 0);
	sort(sum2.begin(), sum2.end());
	for(int i = 0;  i< sum1.size(); i++){
	    long long num = C - sum1[i];
	    ans += upper_bound(sum2.begin(), sum2.end(), num)-sum2.begin();
        //백터에서의 상대적 위치를 찾는 방법
	}
	cout << ans;
}

int main() {
	cin.tie(0);
	cout.tie(0);
	cin >> N >> C;
	for(int i = 0; i < N; i++) cin >> weight[i];
	solve();
	return 0;
}

 

 

 질문 및 조은은 댓글을 남겨주세요