c언어 7453번 합이 0인 네 정수 (백준)

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

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

int main(void) {
	int n, nn;
	scanf("%d",&n);
	nn = n*n;
	int arr[4][n],L[nn],R[nn];
	for(int i=0;i<n;i++)scanf("%d %d %d %d",&arr[0][i],&arr[1][i],&arr[2][i],&arr[3][i]);
	for(int i=0;i<n;i++) {
		for(int j=0;j<n;j++) {
			L[i*n+j] = arr[0][i] + arr[1][j];
			R[i*n+j] = arr[2][i] + arr[3][j];
		}
	}

	qsort(L,nn,4,cmp);
	qsort(R,nn,4,cmp);

	int left = 0, right = nn-1, tmp, LV,RV,LL,RR;
	long long ans = 0;
	while(left < nn && right >= 0) {
		tmp = L[left] + R[right];
		if(tmp > 0) right--;
		else if(tmp < 0) left++;
		else {
			LV = L[left]; RV = R[right]; LL = 0; RR = 0;
			do {LL++; left++;} while(left < nn && L[left] == LV);
			do {RR++; right--;} while(right >= 0 && R[right] == RV);
			ans += (long long)LL * RR;
		}
	}
	printf("%lld",ans);
	return 0;
}

 

풀이 : MITM

 

브루트포스로 처리하면 4000^4 = 256,000,000,000,000 입니다. 문제에서 주어진 소요시간 한도가 12초 이나 너무나도 부족합니다.

 

이를 해결하기위해 MITM 이라는 쪼개기 기법을 사용할 겁니다.

4000^4 에서 4000^2, 4000^2 개의 각각의 브루트포스를 이용하여, 부분합의 배열을 만듭니다

-- 2 * 4000^2 = 32,000,000

 

그런 다음 구한 두개의 부분합 배열을 오름차순 정렬 한 후, 두포인터를 이용하여 서로의 부분합을 더해서 0이 되는것을 확인합니다. 

 

저는 위의 코드에서 0번 1번 배열의 부분합과, 2번 3번 배열의 부분합을 만든다음, 0번 1번 부분합은 0번 index 부터 2번 3번 부분합은 n*n-1 번 index 부터 시작합니다.

 

만약 두 부분합의 합이 0보다 크면 2,3번 부분합의 index을 감소시키고, 0보다 작다면 0,1번 부분합의 index을 증가시킵니다. 

 

0을 찾았다면, 이제 중복 체크를 해야합니다. 합을 0을 이루도록 하는 것이 0,1번 부분합엔 연속적으로 몇개, 2,3번 부분합엔 연속적으로 몇개인지를 각각 구한다음 이들의 곱을 ans에 누적합니다.

 

중복체크를 하는 이유

 

 

 

 

이래야 정확한 개수를 구할 수 있습니다. 그냥 합이 0이라고 양쪽의 포인터를 옮겨버리면 정확한 처리가 불가합니다.