[BOJ] 1450 냅색문제

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

1450번: 냅색문제

 

문제 제목과 어울리지 않는 풀이 방법을 가진 문제인 것 같다.. ㅋㅋㅋ

 

냅색이라고 해서, DP를 써야하나 했지만 전혀 아니었고 mitm(meet in the middle) 문제였다.

 

일단 한번 나이브하게 생각해보자.

 

먼저, 그냥 모든 경우를 탐색하면 되지 않을까 라는 생각을 하게 된다.

하지만 N이 최대 30이므로 최대 2^30 경우의 수를 탐색해봐야 하고, 이는 대략 10억 정도이기 떄문에, 시간 초과가 날게 뻔하다.

 

그럼 이제 mitm의 아이디어를 가져와서 똑같이 생각해보면 된다.

 

1. 먼저 반을 쪼갠다. (그룹 1, 그룹 2)

2. 반을 쪼갠 후 최대 2^15 개(그룹 1) , 2^15 개(그룹 2)의 경우의 수를 각각 저장한다.

3. 각각의 경우를 탐사하면서, 답을 찾는다.

 

인데, 3번에서 만약 이중 반복문을 이용해 경우의수를 찾는다면 위의 방법과 다를게 없어진다.

 

따라서, 그룹 1을 기준으로 기준으로 반복문을 돌면서 그룹 2에서 이분탐색을 수행하고, 넣을 수 있는 최대 경우를 찾아내면 된다.

 

말로 나타내니 이상하다. 한번 코드를 보자.

 

코드는 아래와 같다.

#include <bits/stdc++.h>

#define for1(s,n) for(int i = s; i < n; i++)
#define for1j(s,n) for(int j = s; j < n; j++)
#define foreach(k) for(auto i : k)
#define foreachj(k) for(auto j : k)
#define pb(a) push_back(a)
#define sz(a) a.size()

using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef vector <int> iv1;
typedef vector <vector<int> > iv2;
typedef vector <ll> llv1;
typedef unsigned int uint;
typedef vector <ull> ullv1;
typedef vector <vector <ull> > ullv2;

ll N, C; // N 물건 수, C 가방의 최대 용량
llv1 V; // 물건 무게 목록

llv1 V1; // 그룹 1
llv1 V2; // 그룹 2

ll mid, ans; // mid: 어느 index를 기준으로 쪼갤지, ans: 답
bool chk[33]; // DFS check array

// 물건 무게 합 경우의 수들을 기록한다.
void g(bool flag) { 
  ll s = 0;
  for1(0, N) {
    if(chk[i]) {
      s += V[i];
    }
  }
  if(flag) V1.pb(s);
  else V2.pb(s);
}

// DFS로 모든 경우의 수를 탐색한다.
void f(int start, int end, int crt, bool flag) {
  if(start > end) return;
  if(crt == end) {
    for1(0, 2) {
      chk[crt] = i;
      g(flag);
    }
  }
  else {
    for1(0, 2) {
      chk[crt] = i;
      f(start, end, crt+1, flag);
    }
  }
}


int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    cin >> N >> C;
    mid = N/2;
    for1(0, N) {
      ll a;
      cin >> a;
      V.pb(a);
    }

    f(0, mid, 0, true); // 그룹 1의 경우의 수 탐색
    memset(chk, false, N);
    f(mid+1, N-1, mid+1, false); // 그룹 2의 경우의 수 탐색

    if(V2.empty()) V2.push_back(0);
    sort(V1.begin(), V1.end());
    sort(V2.begin(), V2.end());

    for1(0, V1.size()) { // 그룹 1을 기준으로 탐색한다.
      ll mx = C - V1[i]; // 해당 경우의 수대로 물건을 넣었을 때 남는 용량
      ans += upper_bound(V2.begin(), V2.end(), mx) - V2.begin();
      // 남는 용량에 따라 넣을 수 있는 최대 그룹을 이분 탐색으로 찾는다. (인덱스가 곧 경우의 수가 된다.) 
    }

    cout << ans;
}

 

끝