냅색문제 (feat. 백준, 1450번)

냅색문제
https://www.acmicpc.net/problem/1450

1450번: 냅색문제

 

반응형

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
long long arr[30];
vector<long long> arr1, arr2;
void comb(register int l, register int r, vector<long long>& tmp, register int long long sum) {
    if (l > r) {
        tmp.push_back(sum);
        return;
    }
    comb(l + 1, r, tmp, sum);
    comb(l + 1, r, tmp, sum + arr[l]);
}
int main() {
    ios::sync_with_stdio(false), cin.tie(NULL);
    register int N, C;
    cin >> N >> C;
    for (register int i = 0; i < N; i++)
        cin >> arr[i];
    comb(0, N / 2, arr1, 0), comb(N / 2 + 1, N - 1, arr2, 0);
    sort(arr2.begin(), arr2.end());
    register long long ans = 0;
    for (register int i = 0; i < arr1.size(); i++)
        ans += upper_bound(arr2.begin(), arr2.end(), C - arr1[i]) - arr2.begin();
    cout << ans;
    return 0;
}
// *&)*@*

처음 본 'meet in the middle' 알고리즘을 사용하여 풀이하는 문제라고 합니다.

해당 알고리즘에 대한 설명은 아래 링크로 대체합니다.

[알고리즘 기법] Meet In The Middle