c언어 1093번 스티커 수집 (백준)

#include <stdio.h>
#include <stdlib.h>

int n,m,mid,leftCnt,rightCnt,leftPoint,rightPoint;
long long ans = 1e18, k, tmp, P[32],V[32], budget=0;

typedef struct A{
	long long price, value;
}A;

int cmp(const void*a, const void*b) {
	long long c = ((A*)a)->value - ((A*)b)->value;
	if(c>0) c=1; else if(c<0) c=-1; else c=0;
	return (int)c; 
}

void calSub(int subCnt, int offset, A save[]) {
	int gray, prevGray = 0, diff, changeBitIndex;
	long long value = 0;
	long long price = 0;
	save[0].value = value;
	save[0].price = price;
	
	for(int i=1;i<subCnt;i++) {
		gray = i^i>>1;
		diff = gray ^ prevGray;
		changeBitIndex = __builtin_ctz(diff);
		
		if(gray >> changeBitIndex & 1) {
			value += V[changeBitIndex+offset];
			price += P[changeBitIndex+offset];
		}
		else {
			value -= V[changeBitIndex+offset];
			price -= P[changeBitIndex+offset];
		}
		
		save[i].price = price;
		save[i].value = value;
		
		prevGray = gray;
	}
	return;
}

int main(void) {
	scanf("%d",&n);
	for(int i=0;i<n;i++)scanf("%lld",&P[i]);
	for(int i=0;i<n;i++)scanf("%lld",&V[i]);
	scanf("%lld",&k);
	scanf("%d",&m);
	for(int i=0;i<m;i++){
		int j;
		scanf("%d", &j);
		budget += P[j];
	}
	
	mid = (n+1)/2;
	leftCnt = 1<<mid; rightCnt = 1<<(n-mid);
	leftPoint = 0; rightPoint = rightCnt - 1;
	
	A * left = (A*) malloc(sizeof(A)*leftCnt);
	A * right = (A*) malloc(sizeof(A)*rightCnt);

    //1. Meet in the middle
	calSub(leftCnt, 0, left);
	calSub(rightCnt, mid, right);
	
	//2. sort (order by value)
	qsort(left, leftCnt, sizeof(A), cmp);
	qsort(right, rightCnt, sizeof(A), cmp);
	
	//3. monotone minimize
	for(int i=rightCnt; --i>0;) if(right[i-1].price > right[i].price) right[i-1].price = right[i].price; 
	
	//4. binary search
	for(int i=0;i<leftCnt;i++) {
		int l=0,r=rightCnt-1;
		long long diff=k-left[i].value;
		tmp=1e18;
		
		if(diff > right[rightCnt-1].value); 
		else {
			if(diff<=0) tmp=0;
			else {
				while(l<=r) {
					m = (l+r)/2;			
					if(diff > right[m].value) {
						l = m+1;
					} else {
						tmp = right[m].price;
						r = m-1;
					}
				}
			}
			tmp += left[i].price;
			if(ans > tmp) ans = tmp;
		}
	}
	
	if(ans == 1e18) ans = -1;
	else {
		ans-=budget;
		if(ans<0)ans=0;
	}
	
	printf("%lld",ans);
	free(left); free(right);
	return 0;
}

 
풀이 : MITM, 비트마스크, 정렬, 이분탐색 ( binary search on monotone predicate)
 
 
1. 브루트포스로 풀기엔 2^32 나 걸립니다!!!! 이를 해결하기위해 MITM 즉 둘로 쪼개줍니다. 2 * 2^16
 
부분합을 구할 때, (가치, 가격) 쌍으로 저장해줍니다. 문제에서 스티커들의 가치의 합이 k이상이면서 최소 가격(비용)을 구하는 것 이기 때문입니다. 
 
2. 위에서 구한 둘로 쪼개서 얻어낸 (가치, 가격) 배열 두개를 가치를 기준으로 오름차순 정렬합니다.
 
3. binary search on monotone predicate 을 하여 가치의 합이 k이상이면서 최소 비용인 것을 구합니다.
 
브루트 포스로 찾기엔 2^16 * 2^16 = 2^32 (이러면 MITM 을 한 이유가 없으며, 시간초과이다) 시간이 너무 많이 소요된다.
 
이를 binary search on monotone predicate 을 이용하여 O(n) + O(n log n) 으로 처리해야 한다.
 
이는 두 개의 배열 중 하나를 단조적 술어(Monotone predicate)로 만든 다음, 이분탐색을 적용하는 알고리즘 입니다.
[ 입력이 증가할 때 출력이 증가하거나 유지되는 속성을 가진 술어(함수) ] 
 
먼저 하나의 배열을 단조적 술어로 만드는 것은 쉽습니다.
 
가장 뒤에서 부터 바로 앞에 있는 값이 더 크다면, 더 뒤에 있던 갚으로 덮어 씌워주면 됩니다.
 

value 1 1 3 4 5 6
price  4 2 7 5 4 3

이런 경우

value 1 1 3 4 5 6
price  2 2 3 3 3 3

이 된다.
 
왜 이것을 사용하나면, 이분탐색이 사용되려면 정렬된 상태이거나, 단조 함수인 상태 일때만 적용이 가능하며, 최소값을 구할때 단조 함수로 만드는게 매우 유용하기 때문입니다.

이렇게 단조함수로 만드는게 허용되는 이유는, 일정 가치 이상이며 최소 가격(비용) 을 구하는 것 이므로, 

value 가 더 큰데 price가 같거나 더 작다면, 당연히 이걸 선택합니다. value가 더 작다면, 부득이하게 다른 스티커를 붙여아 할 수 있기 때문입니다.


이렇게 단조 함수로 만든 것에 이분탐색을 적용해봅시다. 


value 1 1 3 4 5 6
price  2 2 3 3 3 3 

MITM 에서 만든 두 개 의 배열들중, 저는 오른쪽 배열을 단조 함수로 만들었으며, 왼쪽 배열의 요소들을 하나씩 이분탐색을 돌렸습니다.

case 1 : 오른쪽 배열에서 가장 가치가 많은 것보다 k - 왼쪽 요소의 가치 가 더 큰 경우 -> 가능한 경우가 없다.
case 2 : k-왼쪽 요소의 가치 <= 0 인 경우 -> 오른쪽 배열에 있는 스티커들을 붙일 필요가 없다 -> 왼쪽꺼만 붙인다.
case 3 : 이분탐색을 이용합니다.
case 3-1 :  k-왼쪽 요소의 가치 > 오른쪽 요소의 가치 라면, 더 높은 가치가 필요하므로 중앙 기준 오른쪽을 탐색합니다.
case 3-2 :   k-왼쪽 요소의 가치 <= 오른쪽 요소의 가치 라면, 일단 k 이상의 가치에 도달했으며, 이때의 가격을 tmp에 저장합니다. 그런 다음, 더 작은 가격으로 조건을 만족한채 가능한지 중앙 기준 왼쪽을 탐색합니다.

case 2,3 의 경우
하나의 왼쪽 요소를 처리 할 때 마다 기존의 ans보다 tmp 가 더 작다면 ans = tmp 을 해줍니다.

 
4.1 ans가 만약 처음 초기값 (변하지 않음, 대입된 적이 없음) 이라면 가능한 경우가 없다는 의미이므로 -1을 대입합니다.
4.2 가능한 경우가 있던 경우, 처음 입력에서 주어진 (5,6번째에 가지고 있는 스티커 개수와, 스티커 종류를 입력으로 줍니다. -> 이걸 다 팔아서 돈으로 바꿨습니다) ans 에 budget을 빼서, 진짜로 필요한 돈을 구합니다. 단 여기서 ans < 0  인 경우 ans = 0 을 해줍니다.
 
5.  ans을 출력한 이후, 동적할당을 해제하고 프로그램을 종료합니다.