c언어 1450번 냅색문제 (백준)

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

int n,mid,leftCnt,rightCnt,leftPoint,rightPoint;
long long ans = 0, c, tmp, arr[30];

long long cmp(const void*a, const void*b) {
	return *(long long*)a-*(long long*)b;
}

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

int main(void) {
	scanf("%d %lld",&n,&c);
	for(int i=0;i<n;i++)scanf("%lld",&arr[i]);
	
	mid = (n+1)/2;
	leftCnt = 1<<mid; rightCnt = 1<<(n-mid);
	leftPoint = 0; rightPoint = rightCnt - 1;
	
	long long * left = (long long*) malloc(sizeof(long long)*leftCnt);
	long long * right = (long long*) malloc(sizeof(long long)*rightCnt);

	calSub(leftCnt, 0, left);
	calSub(rightCnt, mid, right);
	
	qsort(left, leftCnt, 8, cmp);
	qsort(right, rightCnt, 8, cmp);
	
	while(leftPoint < leftCnt && rightPoint >=0) {
		tmp = left[leftPoint] + right[rightPoint];
		if(tmp > c) --rightPoint;
		else {
			ans += rightPoint + 1;
			++leftPoint;
		}
	}
	
	printf("%lld",ans);
	free(left); free(right);
	return 0;
}

 

풀이 : Meet in the Middle, 비트마스킹, gray code, 정렬, 두 포인터

 

0. 브루트포스 론 2^30 이나 걸리므로 이를 2^15, 2^15 즉 반으로 쪼갠 다음, 각 각의 수열에서의 모든 부분합을 구한다음, 이것들을 두 포인터를 이용하여 다시 합치면서, c 이하인 경우가 몇개 있는지를 계산합니다.

 

1. 입력을 받고, 필요한 배열을 동적할당 받습니다.

2. Meet in the middle 을 적용하기 위해, graycode (비트마스킹) 을 이용하여 부분 수열의 부분합들을 계산 한 후 동적할당 받은 배열에 집어 넣습니다.

2.1 반드시 배열의 처음은 공집합을 집어 넣어야 합니다!!!!!! 

3. 부분합들을 가지고 있는 배열들을 오름차순 정렬합니다.

4. 두 포인터로 c 이하인 경우를 계산합니다.

4.1 왼쪽, 오른쪽 부분수열의 부분합을 담은 배열로 구분하고, 왼쪽은 0번부터, 오른쪽은 마지막 부터 시작합니다.

4.2 두 부분합의 합을 계산한 후, c 보다 크다면, 값을 줄이기 위해 오른쪽 index을 -1 합니다.

4.3 만약 c 이하라면 현재 오른쪽 배열을 가리키고 있는 포인터의 값 에 + 1한 값을 ans에 누적합니다.

4.4 그런 다음, 왼쪽 배열의 인덱스를 1 증가시킵니다

5. 결과를 출력 후, 동적할당을 해제 합니다.