Algorithm in A..Z - Meet In The Middle

개념

Meet In The Middle 1

파란점에서 빨간점까지 탐색한다고 생각할 때 파란점 기준으로 탐색하면 초록색 영역만큼 탐색해야한다.

Meet In The Middle 2

하지만 파란점과 빨간점을 기준으로 만나는 노란색 점을 탐색하면 탐색해야 하는 불필요한 영역이 줄어든다.

 

이처럼 기준을 바꿔서 다르게 생각하면 좀 더 연산을 줄일 수 있다.

---

문제

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

1450번: 냅색문제

---

코드

#include <bits/stdc++.h>
using namespace std;

int n, c;
vector<int> input;

vector<int> l, r;
void dfs(int begin, int end, int sum, vector<int> &ve) {
    if (sum > c) {
        return;
    }

    if (begin == end) {
        if (sum != 0LL) {
            ve.push_back(sum);
        }

        return;
    }

    dfs(begin + 1, end, sum, ve);
    dfs(begin + 1, end, sum + input[begin], ve);
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);

    cin >> n >> c;
    input.resize(n);
    for (auto &i : input) {
        cin >> i;
    }

    dfs(0, n / 2, 0, l);
    dfs(n / 2, n, 0, r);

    int ans = l.size() + r.size() + 1;
    sort(r.begin(), r.end());
    for (auto &i : l) {
        ans += upper_bound(r.begin(), r.end(), (c - i)) - r.begin();
    }

    cout << ans << "\n";
}