c언어 2087번 암호문 (백준)

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

int arr[40],n,k,mid,tmp,leftCnt,rightCnt,leftPoint,rightPoint;

typedef struct A{
	int sum; //부분합
	int bit; //어떤 수를 더했는지를 나타내는 비트마스크
}A;

int cmp(const void*a, const void*b) { //주의:비교함수는 정수를 반환해야함.
	return ((A*)a)->sum - ((A*)b)->sum; 
    //. , -> 의 우선순위가 () casting 보다 높다!! 
    //고로 괄호를 씌어준 다음 casting 후, 구조체 포인터 연산자가 작동되도록 한다.
}

void calSub(int subCnt, int offset, A save[]) {
	int gray=0, prevGray=0, diff, changeBitIndex, sum=0;
	save[0].sum = sum;
	save[0].bit = gray;
	
	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 = sum;
		save[i].bit = gray;
		prevGray = gray;
	}
	return;
}

int main(void) {
	scanf("%d",&n);
	for(int i=0;i<n;i++)scanf("%d",&arr[i]);
	scanf("%d",&k);
	
	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);
	//두개로 쪼갠 다음 각 각의 부분합 구하고 배열에 따로 저장 (어떤 수를 더했는지도 따로 저장)
	calSub(leftCnt, 0, left);
	calSub(rightCnt, mid, right);
	//정렬
	qsort(left, leftCnt, sizeof(A), cmp);
	qsort(right, rightCnt, sizeof(A), cmp);
	
	while(leftPoint < leftCnt && rightPoint >= 0) { //두포인터
		tmp = left[leftPoint].sum + right[rightPoint].sum;
		if(tmp > k) --rightPoint; 
		else if(tmp < k) ++leftPoint;
		else break; //찾았다면 (부분합 == k) 두포인터 종료
	}
	//어떤 수가 사용되었는지를 출력 (사용되었다면 1, 아니라면 0)
	for(int i=0; i<mid;i++) printf("%d",left[leftPoint].bit>>i & 1);
	for(int i=0; i<n-mid;i++) printf("%d",right[rightPoint].bit>>i & 1);
	free(left); free(right); //동적할당 해제
	return 0;
}

 

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

 

0. 입력을 받고 필요한 배열들을 동적할당하고, 변수들을 초기화 합니다.

1. 입력받은 수열을 절반으로 쪼개 두개를 만든 다음 각각의 수열에 대한 부분합을 구하고, 어떤 수로 이루어 졌는지를 비트마스크로 나타낸 것 2 개의 값을 구조체 타입의 배열에 저장합니다. (반드시 처음 값은 공집합 0 이어야 합니다)

2. 부분합을 기준으로 오름차순 정렬합니다.

3. 두포인터를 사용하여 두 수열의 부분합들의 합이 k 인 것을 찾으면 종료합니다.

4. 합이 k을 이룰 때, 왼쪽 부분합부터 어떤 수들이 더해져서 이루어 졌는지를 1, 0 으로 나타내면서 출력합니다.

5. 동적할당을 해제하고 종료합니다.