c언어 1208번 부분수열의 합 2 (백준)

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

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

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

void calSub(int subCnt, int offset, int save[]) { //두개로 쪼갠 수열에서, 부분수열의 합 구하기
	int gray, prevGray=0, diff, changeBitIndex; //gray code (비트마스크)
	int sum=0; //부분수열의 합
	save[0] = sum; //공집합 추가 
	for(int i=1;i<subCnt;i++) { //부분수열에서 만들수 있는 합을 계산하고 추가합니다.
    
    	//gray code : 일반적인 비스마스크보다 좀 더 빠른 연산입니다. 
		gray = i^i>>1;
		diff = gray ^ prevGray; //어떤 하나의 비트가 바뀌었는지를 구하기 위한 처리입니다.
		changeBitIndex = __builtin_ctz(diff); //비트가 1인 곳의 index를 반환합니다.
		
        //변한 비트가 1로 변했다면, 그 부분에 대한 arr[]의 값을 sum에 추가, 반대 라면 빼줍니다.
		if (gray >> changeBitIndex & 1) sum += arr[changeBitIndex+offset]; 
        else sum -= arr[changeBitIndex+offset];
		
        //부분수열에서 만들 수 있는 합을 담는 배열에 저장합니다.
		save[i] = sum;
        
        //이전 gray를 갱신합니다.
		prevGray = gray;
	}
	return;
}

int main(void) {
	scanf("%d %d",&n,&k);
	for(int i=0;i<n;i++)scanf("%d",&arr[i]);
	
	mid = (n+1)/2;
	leftCnt  = 1<<mid; rightCnt = 1<<n-mid; //둘 로 쪼개서 나온 부분수열의 모든 합의 개수 + 1 구하기
	leftPoint = 0;     rightPoint = rightCnt-1; //나중에 아래서 두포인터 쓸 때 사용할 변수
    
    //부분수열의 모든 합을 담을 배열 동적할당
	int * left  = (int*) malloc(sizeof(int)*leftCnt);
	int * right = (int*) malloc(sizeof(int)*rightCnt);
	
    //각 각 부분수열의 모든합 계산
	calSub(leftCnt,0,left);
	calSub(rightCnt,mid,right);
	
    //각 각 부분수열의 모든합 오름차순 정렬
	qsort(left,leftCnt,4,cmp);
	qsort(right,rightCnt,4,cmp);
	
    //두 포인터
    //왼쪽수열은 작은값부터, 오른쪽 수열은 큰 값부터
	while(leftPoint<leftCnt && rightPoint>=0) { //어느 한쪽의 포인터가 범위를 넘어가면 종료
		tmp = left[leftPoint] + right[rightPoint]; //두 수열의 합들을 합칩니다.
		if(tmp < k) ++leftPoint; //찾고자 하는 값보다 작다면 왼쪽 수열의 포인터를 오른쪽으로
		else if(tmp > k) --rightPoint; //더 크다면 오른쪽 수열의 포인터를 왼쪽으로
		else { //찾았다면, 중복 체크를 합니다. 
        	//부분수열의 합의 값이 갔더라도 이를 만드는 방법이 여러가지인 경우가 있기 때문입니다.
            //ex) 1 2 3 4 라면 5 는 1,4  2,3 이렇게 2번 만들어 졌습니다. (위에서)
			
            //중복 개수를 구하기 시작합니다.
            LCnt=0;RCnt=0; 
            
            //먼저 비교에 쓸 값을 미리 저장합니다.
			Lvalue = left[leftPoint]; 
			Rvalue = right[rightPoint];
            
            //반복문을 이용하여 포인터를 1씩 증가시키거나(왼쪽수열), 1씩 감소시키면서(오른쪽수열)
            //중복인지 아닌지를 확인합니다.
			do {++LCnt; ++leftPoint;}while(leftPoint<leftCnt && left[leftPoint] == Lvalue);
			do {++RCnt; --rightPoint;}while(rightPoint>=0 && right[rightPoint] == Rvalue);
			
            //결과를 ans에 누적합니다.
            ans += LCnt * RCnt;
		}
	}

	//아래 코드가 필요한 이유!
    //처음 수열들의 모든합을 구할 때, 공집합 0 을 추가했었습니다.
    //공집합을 추가한 이유는 두 포인터는 왼쪽 오른쪽 의 합을 더해서 구하는 원리이나
    //굳이 찾고자 하는 값이 왼쪽 또는 오른쪽 수열의 부분합 자체로 존재할 수도 있기 때문입니다.
    //이를 두포인터에서 한번에 구하고자 공집합을 추가했었습니다.
    //그러나 찾고자 하는 값이 0 인 경우, 두포인터는 공집합 또한 수열에서 만든 0이라고 판단합니다.
    //ex) 1 2 1 2 이라는 수열이 있다면 이를 1 | 1 로 쪼개고 처음에 공집합을 추가하니
    // 0 1 2 3   |  0 1 2 3 이라는 왼쪽, 오른쪽 수열의 부분합을 담은 배열이 생성
    // 찾고자 하는 값이 0 이므로 1 2 1 2 수열에서는 절대로 불가하나, 공집합을 추가했다보니 
    //두포인터는 0,0 을 더하여 1개가 가능하다고 판단합니다.
    //이를 해결하기위해 찾고자 하는 값이 0 이라면 1을 빼줍니다.
	if(k==0) --ans;
    
    
	printf("%lld", ans);
	free(left); free(right);
	return 0;
}

 

풀이 : Meet in the Middle (MITM), gray code, 비트마스크

 

 

주된 설명은 코드 주석에 나와 있습니다.

 

최대 2^40 의 경우를 브루트 포스로 구하기엔 너무나 많은 시간이 소비됩니다. 그러나 이를 두개로 가르면 2^20, 2^20 + 정렬 + 두포인터 ... 이므로 브루트포스보다 더 빨리 해결이 가능하게 됩니다.

 

이에 대한 대표적인 알고리즘이 MITM 입니다.

 

1. 수열을 중간에서 2개로 쪼갠다.

2. 각각의 수열에서 만들수 있는 부분합들을 구한다. 이를 각 각 정렬한다.

3. 두포인터를 이용하여 각각의 수열에서 얻은 부분합들을 서로 더해서 비교한다.

 

이런 과정을 거칩니다.

 

물론 찾고자 하는 값이 각각의 수열에 있는 부분합들을 더할 필요가 없는 경우(수열 쪼개서 구한 부분합이 찾고자 하는 값) 도 존재하니, 2 과정에서 공집합 (값이 0인) 을 추가해줍니다! 이를 추가하면 간편하게 찾고자 하는 값이  각각의 수열에 있는 부분합들을 더할 필요가 없는 경우 를 해결할 수 있습니다.