궤도
[백준] 1450번 : 냅색문제 본문
문제
풀이
한 물건에 대해 우리는 그 물건을 넣거나 넣지 않는 2가지 조치만 취할 수 있다.
근데 물건들은 최대 30개까지 들어올 수 있고 이 경우 2^30회의 연산을 해야한다.
이럴 때 사용하는 알고리즘이 meet in the middle이라고 한다. 난 처음 들어봤다.
www.secmem.org/blog/2019/03/08/meet-in-the-middle/
이런 설명이 있다.
그니까 배열을 둘로 쪼개서 연산을 하란 건데...
그럼 일단 2^30회의 연산이 2^16회의 연산으로 줄어들었다.
더 이상 말로 떠드는건 너무 어려우니 예제로 알아보자.
4 6
1 5 3 2
이런 입력이 들어왔다고 하자. 배열을 둘로 쪼개면 1 5 | 3 2 로 쪼개지겠다.
(1, 5)에 대해 가능한 모든 조합의 무게를 구하면 {0, 1, 5, 6}이다.
(3, 2)에 대해 가능한 모든 조합의 무게를 구하면 {0, 3, 2, 5}이다.
(1, 5)의 조합을 front, (3, 2)의 조합을 back이라고 하자.
front[0] = 0에 대해 가능한 back[i]는 i=0, 1, 2, 3 총 4개이다.
front[1] = 1에 대해선 i=0, 1, 2, 3이고
front[2] = 5에 대해선 i=0
front[3] = 6에 대해선 i=0
이렇게 총 10개가 나온다.
근데 front[i] 하나하나에 대해 모든 back 배열을 탐색하는건 좋아보이지 않는다.
그래서 back 배열을 정렬한다.
{0, 2, 3, 5}
C=6이고 front[i]=k라면 이 이상 담을 수 있는 최대 무게는 C-k이다.
back 배열에서 key값 C-k를 가지고 upper_bound를 찾으면 그게 조건에 맞는 back 배열 원소의 수다.
소스코드
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
vector<ll> arr;
vector<ll> splitArr(int left, int len) { //비트 마스킹으로 각 배열에 대한 연산
vector<ll> result;
for (int i = 0; i < (1 << len); i++) {
ll sum = 0;
for (int j = 0; j < len; j++) {
if (((1 << j) & i) != 0)
sum += arr[left + j];
}
result.push_back(sum);
}
return result;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
int N, C, result = 0;
cin >> N >> C;
arr.assign(N, 0);
for (int i = 0; i < N; i++)
cin >> arr[i];
vector<ll> front_arr = splitArr(0, N / 2); //앞의 절반
vector<ll> back_arr; //뒤의 절반
if (N % 2 == 0) //배열의 크기가 짝수일 때
back_arr = splitArr(N / 2, N / 2);
else //배열의 크기가 홀수일 때
back_arr = splitArr(N / 2, N / 2 + 1);
sort(back_arr.begin(), back_arr.end()); //정렬
for (int i = 0; i < front_arr.size(); i++) //back_arr에서 C-front_arr[i]에 대한 upper_bound 찾기
result += upper_bound(back_arr.begin(), back_arr.end(), C - front_arr[i]) - back_arr.begin();
cout << result;
}
전체 소스코드다.
vector<ll> front_arr = splitArr(0, N / 2); //앞의 절반
vector<ll> back_arr; //뒤의 절반
if (N % 2 == 0) //배열의 크기가 짝수일 때
back_arr = splitArr(N / 2, N / 2);
else //배열의 크기가 홀수일 때
back_arr = splitArr(N / 2, N / 2 + 1);
sort(back_arr.begin(), back_arr.end()); //정렬
splitArr이란 함수로 배열의 앞의 절반과 뒤의 절반에 대한 연산을 했다.
배열의 크기가 홀수인 경우를 신경써야 한다.
vector<ll> splitArr(int left, int len) { //비트 마스킹으로 각 배열에 대한 연산
vector<ll> result;
for (int i = 0; i < (1 << len); i++) {
ll sum = 0;
for (int j = 0; j < len; j++) {
if (((1 << j) & i) != 0)
sum += arr[left + j];
}
result.push_back(sum);
}
return result;
}
splitArr 함수는 비트마스크로 연산을 한다.
len = 3이라면 000~111까지 비트를 증가하며 모든 경우를 고려한다.
for (int i = 0; i < front_arr.size(); i++) //back_arr에서 C-front_arr[i]에 대한 upper_bound 찾기
result += upper_bound(back_arr.begin(), back_arr.end(), C - front_arr[i]) - back_arr.begin();
마지막으로 C-front_arr[i]를 key값으로 back_arr에서 upper_bound를 찾으며 result 변수를 갱신하면 된다.