BOJ 14889 : 스타트와 링크 (삼성 SW TEST A형)

삼성 A형 전체 링크

 

www.acmicpc.net/workbook/view/1152 (A형 문제집)

 

www.acmicpc.net/problem/14889

 

 

N개의 팀 중, N / 2를 선택해야 하는 조합 문제이다.

조합 문제에서는 list에 경우의 수를 저장했지만, 여기에서는 visit 배열을 이용해 선택한 팀을 1로 체크하자.

그러면 visit = 0인 팀은 저절로 다른 팀이 된다.

 

마지막으로 선택된 팀(start), 선택되지 않은 팀(link)에 대해 입력받은 표를 보고 점수를 계산해주면 된다.

start 팀은 team 배열의 앞에, link 팀은 team[halfN] 부터 저장하자.

#include <stdio.h>

#define MAX (20 + 5)

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

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 team[MAX * 2] = { 0 };
	int sum1, sum2, scnt, lcnt;

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

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

	return abs(sum1, sum2);
}

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

		if (tmp < MIN) MIN = 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)
{
	input();

	DFS(1, 0);

	printf("%d\n", MIN);
	
	return 0;
}

 

실제 A형에서 MIN을 초기화 하는 것을 잊지 말자.