[코드트리] 조삼모사 (삼성 SW 역량테스트 2017 하반기 오전 1번)

 

A형 필수 알고리즘을 체계적으로 배우고 싶다면? (인프런 바로가기)

 

삼성 A형 전체 링크

 

https://www.codetree.ai/training-field/frequent-problems/problems/three-at-dawn-and-four-at-dusk

이후 설명 및 입/출력은 링크 참고

 

조삼모사 문제 풀이는 BOJ 14889 : 스타트와 링크와 같다.

#include <stdio.h>

#define MAX (20 + 5)

int T, N, halfN;
int MAP[MAX][MAX];
int visit[MAX];
int minAnswer;

void input()
{
	scanf("%d", &N);

	halfN = N / 2;
	for (int r = 0; r < N; r++)
		for (int c = 0; c < N; c++)
			scanf("%d", &MAP[r][c]);
}

int abs(int a, int b)
{
	return (a > b) ? a - b : b - a;
}

int minValue()
{
	int pair[MAX * 2] = { 0 };
	int sum1, sum2, scnt, lcnt;

	scnt = lcnt = 0;
	for (int i = 0; i < N; i++)
	{
		if (visit[i]) pair[scnt++] = i;
		else pair[halfN + lcnt++] = i;
	}

	sum1 = sum2 = 0;
	for (int r = 0; r < halfN; r++)
	{
		for (int c = r + 1; c < halfN; c++)
		{
			sum1 += MAP[pair[r]][pair[c]] + MAP[pair[c]][pair[r]];
			sum2 += MAP[pair[r + halfN]][pair[c + halfN]] + MAP[pair[c + halfN]][pair[r + halfN]];
		}
	}

	return abs(sum1, sum2);
}

void DFS(int L, int st)
{
	if (L > halfN)
	{
		int tmp = minValue();

		if (tmp < minAnswer) minAnswer = tmp;

		return;
	}

	for (int i = st; i < N; i++)
	{
		if (visit[i] == 1) continue;

		visit[i] = 1;
		DFS(L + 1, i);
		visit[i] = 0;
	}
}

int main(void)
{
	// scanf("%d", &T);
	T = 1;
	for (int tc = 1; tc <= T; tc++)
	{
		input();
		minAnswer = 0x7fff0000;

		DFS(1, 0);

		printf("%d\n", minAnswer);
	}

	return 0;
}