c언어 4160번 이혼 (백준)

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

typedef struct A{
	int diff, sell;	
}A;

int arr[24];
A left[531441], right[531441];

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

void dfs(int cnt, int goal, int offset, int diff, int sell, int* point, A save[]) {
	if(cnt == goal) {
		save[*point].diff = diff;
		save[*point].sell = sell;
		(*point)++;
		return;
	}
	dfs(cnt+1,goal,offset,diff+arr[cnt+offset],sell,point,save);
	dfs(cnt+1,goal,offset,diff-arr[cnt+offset],sell,point,save);
	dfs(cnt+1,goal,offset,diff,sell+arr[cnt+offset],point,save);
}

int main(void) {
	while(1) {
		int n,mid,sumDiff,leftCnt=0,rightCnt=0,leftPoint,rightPoint,ans=2e9;
		scanf("%d",&n);
		if(!n) break;
		for(int i=0;i<n;i++) scanf("%d",&arr[i]);
	
		mid = (n+1)/2;	
		dfs(0,mid,0,0,0,&leftCnt,left);
		dfs(0,n-mid,mid,0,0,&rightCnt,right);
		leftPoint = 0; rightPoint = rightCnt - 1;
		
		qsort(left,leftCnt,sizeof(A),cmp);
		qsort(right,rightCnt,sizeof(A),cmp);
		
		while(leftPoint < leftCnt && rightPoint >= 0) {
			sumDiff = left[leftPoint].diff + right[rightPoint].diff;
			if(sumDiff > 0) rightPoint--;
			else if(sumDiff < 0) leftPoint++;
			else {
				int leftDiff=left[leftPoint].diff,rightDiff=right[rightPoint].diff,leftSell=2e9,rightSell=2e9;
				do {leftSell=leftSell<left[leftPoint].sell?leftSell:left[leftPoint].sell;leftPoint++;}while(leftPoint < leftCnt && leftDiff == left[leftPoint].diff);
				do {rightSell=rightSell<right[rightPoint].sell?rightSell:right[rightPoint].sell;rightPoint--;}while(rightPoint >= 0 && rightDiff == right[rightPoint].diff);
				leftSell += rightSell;
				ans = ans<leftSell?ans:leftSell;
			}
		}
		printf("%d\n",ans);
	}
}

 

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

 

0. n을 입력받습니다. 만약 0이 들어오면 프로그램을 종료합니다.

 

1. n 의 최댓값은 24, 

1개당 가능한 경우의 수는 3개 (잭에게 집을 줌, 질에게 집을 줌, 집을 팔아버림)

 

브루트포스로 모든 경우를 고려하기엔 3^24 = 282,429,536,481 너무나도 많다. 이를 MITM 을 이용하여

2 * 3^12 = 1,062,882 개로 줄일 수 있다.

 

입력받은 데이터를 중간 기준으로 반으로 나눈다음, 절반씩 dfs을 이용하여 (차이, 집 판매액) 쌍을 만들어 냅니다.

 

여기서 말하는 차이는 제 코드 기준으로, 잭에게 집을 주면 +, 질에게 집을 주면 - 을 하며, 집을 팔 때는 집 판매액에 누적시킵니다. 이러한 (차이, 집 판매액) 쌍들을 구했으면, 차이를 기준으로 오름차순 정렬을 합니다.

 

이렇게 차이를 기준으로 정렬된 두개의 배열들을 가지고 두포인터를 시작합니다.

왼쪽배열은 index 0부터, 오른쪽배열은 가장 마지막 index에서 부터 시작하며, 각각의 쌍들에서 차이의 합을 구합니다.

 

1. diff의 합이 0보다 크다, 이럴땐 오른쪽 배열의 index을 감소

2. diff의 합이 0보다 작다, 이럴 땐 왼쪽 배열의 index을 증가

3. diff의 합이 0 일 때 -> 이 경우가 공평하게 나누는 경우 입니다.

3.1 여기서 중복체크를 진행해야 합니다. (차이, 집 판매액) 쌍 들의 연속으로 이루어진 배열에서, 차이는 같으나, 집 판매액이 서로 상이한 경우가 존재하기 때문입니다. 고로 공평하게 나누는 경우를 찾은 경우엔 diff값이 같은 연속된 쌍들을 확인해보면서 그 중 가장 집 판매액이 낮은 것을 구해내야 합니다. 문제 조건에서 최대한 잭과 질에게 집을 줄려고 하기 때문입니다.

 

 

 

4. 3의 경우를 만족하는 경우 중 집판매액의 합이 가장 적은 값을 출력합니다.