c언어 10958번 Ice Hockey World Championship (백준)

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

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

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

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,&k);
	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 > k) --rightPoint;
		else {
			ans += (long long)rightPoint + 1;
			++leftPoint;
		}
	}
	
	printf("%lld",ans);
	free(left); free(right);
	return 0;
}

 

풀이 : MITM, 비트마스크, 정렬, 두포인터

 

https://h202.tistory.com/1211

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

 

와 동일합니다.

 

단 cmp 비교함수를 사용할 때 

int cmp(const void *a, const void*b) {

    return a-b; 

}

이런식으로 만들면 a,b가 int 범위를 초과할 수 있기 때문에 문제가 발생하므로, 위 코드처럼 따로 정수형으로 바꿔주는 작업이 필요합니다.