(1450) 냅색문제

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

단계별로 풀어보기

30단계(투 포인터) 5번째

 

 

 

MITM(Meet in the middle, 중간에서 만나기) 알고리즘은 브루트 포스를 써야 하지만 경우의 수가 '약간' 클 때 쓸 수 있는 알고리즘이다.

O(2^N)이나 O(N^4)같은 시간복잡도를 가진 알고리즘을 써야 하는데, N의 범위가 시간 초과가 아쉽게 될 정도라고 하자.

이때 N을 절반으로 쪼개 두 구간으로 나눈 뒤 각각의 구간에서 브루트 포스를 쓰고 두 구간을 순회하며 정렬이나 이분 탐색 등으로 합치면 O(N log N)의 시간복잡도가 추가로 곱해지는 대신 N의 범위를 절반으로 줄일 수 있다.

글로 설명하면 어렵지만 MITM 문제는 특유의 애매하게 오버되는 시간 복잡도와 범위가 있어서 PS에 익숙해지면 문제를 봤을 때 MITM틱한 관상(?)이 보인다.

 

 

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
  int n, c, ans= 0;
  
  cin >> n >> c;
  
  vector<long> v(n), a, b;
  
  for(int i=0;i<n;i++)  cin >> v[i];
  
  int n1= n/2, n2= n-n1;
  
  for(int i=0;i<(1<<n1);i++){
    long s= 0;
    
    for(int j=0;j<n1;j++){
      if(i&(1<<j))  s+= v[j];
    }
    
    a.push_back(s);
  }
  
  for(int i=0;i<(1<<n2);i++){
    long s= 0;
    
    for(int j=0;j<n2;j++){
      if(i&(1<<j))  s+= v[n1+j];
    }
    
    b.push_back(s);
  }
  
  sort(a.begin(), a.end());
  sort(b.begin(), b.end());
  
  for(int i=0;i<a.size();i++){
    ans+= upper_bound(b.begin(), b.end(), c-a[i])-b.begin();
  }
  
  cout << ans;
  
  return 0;
}