4012. 요리사

#define ABS(X) ((X > 0) ? (X) : (-X))

using namespace std;

static int N;
static int board[16][16];

static int __solution(int start, int bitmap, int cnt)
{
	if (cnt == N / 2)
	{
		vector<int> material[2];
		for (int i = 0; i < N; i++)
		{
			if ((bitmap & (1 << i))) //0 또는 2^i
				material[1].push_back(i);
			else
				material[0].push_back(i);
		}
		
		int V[2] = { 0, 0 };
		for (int i = 0; i < 2; i++)
		{
			for (int j = 0; j < cnt; j++)
			{
				int m1 = material[i][j];
				//이미 했던 계산을 다시 하지 않기 위해
				for (int k = j + 1; k < cnt; k++)
				{
					int m2 = material[i][k];
					V[i] += (board[m1][m2] + board[m2][m1]);
				}
			}
		}
		int diff = V[0] - V[1];
		return ABS(diff); //매크로 함수 사용 시 가급적 이렇게 사용하도록,
	}
	else
	{
		int min = 0x7fffffff;
		//i를 선택했으면, 다음 재귀에서는 i + 1 부터 선택해야만 함,
		for (int i = start; i < N; i++) 
		{
			int ret = __solution(i + 1, (bitmap | (1 << i)), cnt + 1);
			if (ret < min)
				min = ret;
		}
		return min;
	}
}

static int solution(void)
{
	scanf("%d", &N);
	for (int y = 0; y < N; y++)
	{
		for (int x = 0; x < N; x++)
			scanf("%d", &board[y][x]);
	}

	//첫번째 재료는 무조건 포함되어야 함, A, B 아무나 상관 없음
	return __solution(1, 1, 1); 
}

__solution()에 대해서 정리하면

N개의 재료 중 N/2개를 선택하는 경우를 만들어야 한다.

이 때, 선택된 재료를 저장하기 위해 배열을 사용하는 것도 나쁘지 않으나, 맨 처음 풀었을 때 bitmask 형식으로 이를 대체하여 다시 한번 이 방식으로 풀어보았다.

bitmap 사용 시에는 int의 경우 최대 32개 까지 저장 할 수 있다는 것을 유념해야 한다.

 

먼저 bitmap을 만드는 경우, 즉, 재료를 선택하는 경우를 만드는 것에 대한 것이다.

기본적으로 반복문이 기반이 되나, 첫번째 인덱스의 설정이 우선되야 한다. 

처음 재귀에서 0번 인덱스를 사용하였으면, 그 다음 재귀는 1번 인덱스부터 사용해 나가야하기 때문에, 재귀 호출 시 선택한 인덱스 + 1 을 전달 하는 것이다.

 

다음은 재귀를 종료할 시점이다.

재료는 N개 중 절반만 선택하면 되므로 간단하게 그 시점을 알 수 있다.

문제는 선택한 재료의 시너지를 계산하는 과정이다.

 

전달받은 bimap에서 비트 정보를 추출하여 각기 다른 vector에 선택된 정보를 저장 할 수 있는데,

추출한 bit값은 0아니면 1이 아니라, 0 아니면 2^i 승이 된다. 처음에는 추출된 값을 vector의 인덱스로 하여 push_back 하였는데, 디버깅시 pNext로 인한 에러가 발생하였다. 앞선 글에서 한차레 언급한바 있다.

 

다음은 시너지를 계산하는 방식이다.

1, 2를 선택한 경우 board[1][2] + board[2][1]이 되어야한다.

1, 2, 3를 선택한 경우 board[1][2] + board[2][1] + board[1][3] + board[3][1] + board[2][3] + board[3][2] 가 되야 한다.

(1,2) (1,3) (2,3) 이렇게 시너지를 내므로 위와 같이 계산해야 하는 것이다.

 

그래서 이중 반복문을 돌아 모든 경우를 만들어 내는데, 중첩된 반복문은 바깥쪽 반복문의 "시작인덱스 + 1" 부터 시작하면 된다. (1, 2)에 대해서 역으로도 이미 계산 하였으므로, (2, 1)에 대해서는 신경 쓸 필요가 없기 때문이다.

 

마지막은 __solution()에 시작에 대해서이다.

문제는 A와 B로 나뉘어 재료를 어떻게 나눌 것인가인데, 요구하는 답은 A가 어떻게 재료를 선택하는 것이 아니기 때문에, 일단 0번인덱스, 즉 첫번째 재료는 누가 갖든지 상관이 없게 된다. 그래서 재귀 시작 시에는 1번 인덱스 부터 반복하게 되며, 이미 1이 bitmap에 설정되어 있고, 현재 선택한 재료의 개수도 1이 되는 것이다.

 

//주의사항 및 정리

1. vector배열 사용 시 잘못된 인덱스로 접근 할 경우 발생하는 에러 및 디버깅 시 어떻게 되는지는 여러번 정리하였다.

2. __solution(0, 0, 0)으로 시작해도 큰 문제는 없지만 소요된 시간은 커진다. 이전 글에서 정리한 것처럼, 이렇게 시작해서 시간이 남으면 좀 더 향상 시켜도 된다.

3. 매크로 함수 사용 시 최대한 변수에 값을 담아서 전달 할 것.