BOJ 1450. 냅색문제

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

solved.ac: Gold I (2024.09.10)

깔끔한 구현 연습용으로 풀었습니다.

정렬된 배열이 있을 때, v 이하의 수의 개수는 upper_bound(arr, v) - arr.begin()으로 얻을 수 있습니다.

 

N이 어중간하게 크므로, mitm 기법이 바로 떠오릅니다.

그냥 구현합시다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
typedef long long int LL;

/* 정렬된 배열 arr에서 v 이하의 개수 */
LL findLower(vector<LL> &arr, LL v)
{
  return upper_bound(arr.begin(), arr.end(), v) - arr.begin();
}

/* arr 내의 모든 조합을 찾아 res에 저장 */
void findCases(vector<LL> &arr, vector<LL> &res, int idx = 0, LL cur = 0)
{
  if(idx == arr.size())
  {
    res.push_back(cur);
    return;
  }
  
  findCases(arr, res, idx + 1, cur);
  findCases(arr, res, idx + 1, cur + arr[idx]);
}

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

  LL n, c;
  cin >> n >> c;

  vector<LL> arr1, arr2, res1, res2;
  for(int i = 0; i < n; i++)
    {
      LL cur;
      cin >> cur;
      if(i < n / 2) arr1.push_back(cur);
      else arr2.push_back(cur);
    }

  findCases(arr1, res1); findCases(arr2, res2);
  sort(res2.begin(), res2.end());

  LL cnt = 0;
  for(auto i: res1) cnt += findLower(res2, c - i);
  cout << cnt;
}