BOJ 1450. 냅색문제

🙇‍♀️[Gold I] 냅색문제 - 1450

문제 링크

성능 요약

메모리: 2920 KB, 시간: 8 ms

분류

이분 탐색, 중간에서 만나기

제출 일자

2024년 6월 10일 20:15:43

문제 설명

세준이는 N개의 물건을 가지고 있고, 최대 C만큼의 무게를 넣을 수 있는 가방을 하나 가지고 있다.

N개의 물건을 가방에 넣는 방법의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 C가 주어진다. N은 30보다 작거나 같은 자연수, C는 10⁹보다 작거나 같은 음이 아닌 정수이다. 둘째 줄에 물건의 무게가 주어진다. 무게도 10⁹보다 작거나 같은 자연수이다.

출력

첫째 줄에 가방에 넣는 방법의 수를 출력한다.

🚀풀이

이 문제는 부분 집합을 활용한 조합의 문제로, 주어진 물건들의 무게를 조합하여 최대 무게 C를 초과하지 않는 모든 경우의 수를 계산하는 문제입니다.
물건의 개수가 30개 이하이기 때문에, 이를 효율적으로 해결할 수 있는 방법 중 하나는 “Meet in the Middle” 기법입니다.

• 해결 전략
  • 주어진 물건을 두 그룹으로 나눕니다.
  • 각각의 그룹에서 가능한 모든 부분 집합의 합을 계산합니다.
  • 두 그룹의 합을 조합하여 최대 무게 C를 초과하지 않는 모든 경우의 수를 계산합니다.
• 구현 단계
  • 물건을 두 그룹으로 나눈 후, 각 그룹에서 가능한 모든 부분 집합의 합을 구합니다.
  • 한 그룹의 합을 고정하고, 다른 그룹의 합에서 적절한 값을 이진 탐색으로 찾아 조합하여 최대 무게 C를 초과하지 않는 경우를 계산합니다.
• 입력 처리: N과 C, 그리고 물건의 무게를 입력받습니다.
• 부분 집합 합 계산: calculateSubsets 함수를 이용해 두 그룹으로 나눈 각각의 물건에서 가능한 모든 부분 집합의 합을 계산합니다.
• 이진 탐색을 통한 조합 계산: 첫 번째 그룹의 합을 고정하고, 두 번째 그룹의 합에서 C를 넘지 않는 값을 이진 탐색을 통해 찾아서 모든 가능한 조합을 계산합니다.
• 결과 출력: 계산된 방법의 수를 출력합니다.

몰라서 찾아본건데 봐도 모르겠다.

Meet in the Middle에 대해서 더 찾아봤다.

Meet in the Middle 기법 설명

개념

1. 문제 분할: 주어진 문제를 두 개의 하위 문제로 분할합니다.
2. 부분 집합 계산: 각 하위 문제에서 가능한 모든 부분 집합의 값을 계산합니다.
3. 조합: 두 하위 문제에서 얻은 부분 집합을 적절히 조합하여 최종 문제의 해를 구합니다. 이 방법은 일반적으로 문제의 크기를 절반으로 줄이고, 각 절반에 대해 모든 부분 집합을 계산하여 문제를 해결합니다. 이렇게 하면 원래 문제가 지닌 탐색 공간의 크기를 크게 줄일 수 있습니다.

라고 한다. 아 몰라

🚀코드

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include<iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <math.h>
#include <climits>

using namespace std;

// 주어진 벡터에서 가능한 부분 집합의 합을 모두 구하는 함수
void calculateSubsets(const vector<long long>& weights, vector<long long>& subsets) 
{
    int n = weights.size();
    for (int i = 0; i < (1 << n); ++i) 
    {
        long long sum = 0;
        for (int j = 0; j < n; ++j) 
        {
            if (i & (1 << j)) 
            {
                sum += weights[j];
            }
        }
        subsets.push_back(sum);
    }
}

void solve()
{
    int N;
    long long C;
    cin >> N >> C;

    vector<long long> weights(N);
    for (int i = 0; i < N; ++i) 
    {
        cin >> weights[i];
    }

    // 물건을 두 그룹으로 나누기
    int mid = N / 2;
    vector<long long> group1(weights.begin(), weights.begin() + mid);
    vector<long long> group2(weights.begin() + mid, weights.end());

    vector<long long> subsets1, subsets2;

    // 각 그룹에서 가능한 부분 집합의 합 계산
    calculateSubsets(group1, subsets1);
    calculateSubsets(group2, subsets2);

    // 두 번째 그룹의 부분 집합 합을 정렬
    sort(subsets2.begin(), subsets2.end());

    long long count = 0;

    // 첫 번째 그룹의 부분 집합 합을 순회하며 가능한 조합을 찾기
    for (const auto& sum1 : subsets1) 
    {
        if (sum1 <= C) 
        {
            // subsets2에서 sum1과 합쳐서 C를 넘지 않는 요소의 개수를 찾기
            count += upper_bound(subsets2.begin(), subsets2.end(), C - sum1) - subsets2.begin();
        }
    }

    cout << count << '\n';
}

int main()
{
	FILE* stream;
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	freopen_s(&stream, "input.txt", "rt", stdin);

	solve();

	return 0;
}