c언어 9007번 카누 선수 (백준)

#include <stdio.h>
#include <stdlib.h>
#define abs(x,y) x-y>0?x-y:y-x

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

int main(void) {
	int t,n,nn,k;
	scanf("%d",&t);
	while(t--) {
	scanf("%d %d",&k, &n);
	nn = n*n;
	int arr[4][n], left[nn],right[nn],leftPoint=0,rightPoint=nn-1,sum,diff=1e9,ABS,ans;
	for(int i=0;i<4;i++) for(int j=0; j<n; j++) scanf("%d",&arr[i][j]);
	for(int i=0;i<n;i++) {
		for(int j=0;j<n;j++) {
			left[i*n+j] = arr[0][i] + arr[1][j];
			right[i*n+j] = arr[2][i] + arr[3][j];
		}
	}
	
	qsort(left, nn, 4, cmp);
	qsort(right, nn, 4, cmp);
	
	while(leftPoint<nn && rightPoint >= 0) {
		sum = left[leftPoint]+right[rightPoint];
		ABS = abs(sum,k);
		if(diff > ABS) {
			diff = ABS;
			ans = sum;
		} else if(diff == ABS && ans > sum) ans = sum;		
		
		if(sum > k) rightPoint--;
		else if(sum < k) leftPoint++;
		else break;
	}
	printf("%d\n",ans);
	}
	return 0;
}

 

풀이 : MITM, 두포인터, 정렬

 

0. t를 입력

1. k,n 그리고 여러 arr[4][n] 을 입력받음

2. n^4 를 브루트포스로 비교하기엔 시간이 너무 많이 걸리니, n^2 + n^2 로 계산하기위해, 입력받은 배열들을 절반으로 나눈 다음, 각각 브루트포스를 이용하여 부분합들을 구함.

3. 그 부분합들을 오름차순 정렬함 이는 두포인터에서 사용하기 위함

4. 두포인터로, 만들어 놓은 두개의 부분합을 합침,

-> 단 k 값과 가까운 수를 ans에 저장, ex) k = 300, 이고 ans = 301 일 때, 299 라는 부분합들의 합이 발생하면 301-300 = 1, 300-299 = 1로 차이는 같으나, 문제에서 이런 경우 k값보다 더 작은 수를 출력하라고 했으므로 ans 에 299를 대입한다.

-> 만약 부분합의 합이 k가 나왔다면 더이상 두포인터를 할 필요가 없다.