[C] 백준 14889번 스타트와 링크

 

안녕하세요 :-)

오늘도 삼성 SW 역량 테스트 기출문제를 풀어보았습니다!

 

백준 14889번

www.acmicpc.net/problem/14889

14889번: 스타트와 링크

.

문제의 입력 범위가 4 ≤ N ≤ 20으로 주어졌기 때문에

저는 이번에도 재귀 함수를 사용하여 풀어보았습니다!

이 문제를 수학적으로 접근을 해보자면 n명의 사람을 2개의 팀으로 나누는 것이기 때문에

nC2를 구하는 것과 같다고 할 수 있습니다.

만약 n이 4라고 한다면 아래의 그림과 같이 표현할 수 있습니다.

(아래의 표에서 O는 스타트 팀, △는 링크 팀을 의미합니다!)

n=4일 때

 

여기서 뭔가 공통된 부분이 보이시나요?

공통된 부분 제거

 

위의 그림과 같이 중간의 빨간 선을 기준으로 형식이 동일한 케이스가 있다는 것을 알 수 있습니다.

따라서 우리는 빨간 선을 기준으로 위의 케이스만 구한 다음, 해당 케이스를 빨간 선 기준 아래의 케이스로 한번 더 고려해주면 됩니다.

(O가 스타트 팀인 경우와 링크 팀인 경우 이 2가지로 나누어 생각하면 되겠죠?)

 

n=4일 때 가능한 경우

 

그럼 빨간 선을 기준으로 위에 있는 케이스는 위의 그림과 같이 트리로 표현을 할 수 있고,

적절한 종료 조건을 사용하여 불필요한 검사를 줄일 수 있습니다.

제가 설정한 종료 조건은 아래와 같습니다.

 

depth == n-1 || cnt == n/2일 때 혹은 depth-cnt == n/2일 때

 

여기서 depth는 트리의 depth를 의미하고 저는 0에서부터 시작했기 때문에 n-1까지만 검사를 합니다.

그리고 cnt는 특정 팀의 인원을 의미하며, 각 팀의 인원은 n/2로 같아야 하기 때문에 cnt가 n/2일 때까지만 검사를 하였습니다.

마지막으로 depth-cnt == n/2 조건은 불필요한 케이스를 줄이기 위한 추가 조건으로,

이것 역시 각 팀의 인원이 n/2명이 넘지 않도록 설정해주었습니다.

.

이를 바탕으로 작성한 코드는 아래와 같습니다.

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#define minus(x, y) x>y?x-y:y-x
int n, cap[20][20];
int team[20]; // 스타트 팀와 링크 팀을 구분 짓기 위한 배열
int index = 0; // team 배열의 index
int min = 100;

void calculate() {
	int a1 = 0, b1 = 0; // 1이 스타트 팀일 때
	int a2 = 0, b2 = 0; // 0이 스타트 팀일 때

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (i == j)
				continue;
			if (team[i] == 1 && team[j] == 1) {
				a1 += cap[i][j];
				a2 += cap[j][i];
			}
			if (team[i] == 0 && team[j] == 0) {
				b1 += cap[i][j];
				b2 += cap[j][i];
			}
		}
	}

	int gap1 = minus(a1, b1);
	int gap2 = minus(a2, b2);

	if (gap1 < min)
		min = gap1;
	if (gap2 < min)
		min = gap2;
}
void comb(int depth, int isChoose, int cnt) {

	if (isChoose == 1)
		team[depth] = 1;
	else
		team[depth] = 0;

	if (depth - cnt == n / 2)
		return;
	else {
		if (depth == n - 1 || cnt == n / 2) {
			calculate();
			return;
		}
	}

	// choose O
	comb(depth + 1, 1, cnt + 1);
	// choose X
	comb(depth + 1, 0, cnt);

	return;
}

int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			scanf("%d", &cap[i][j]);

	comb(0, 1, 1);

	printf("%d", min);
}

 

저는 team이라는 배열을 사용하여 전체 인원을 2가지(0 or 1)로 구분하였습니다.

이를 구분짓기 위한 인자로는 isChoose를 사용하였습니다.

그리고 앞서 언급한 트리의 탐색 종료 조건을 활용하여 재귀 함수를 작성하였습니다.

저는 전체 케이스의 절반을 제거하고 시작하였기 때문에 재귀 함수의 시작을 comb(0, 1, 1)로 설정하였습니다.

마지막으로 적절한 종료 조건에 다다른 케이스(전체 인원이 정확히 2개의 팀으로 나누어진 경우)는 calculate() 함수를 통해 팀 간의 능력치 차이를 계산하였습니다.

이때 앞서 제거한 절반의 케이스(빨간 선 기준 아래의 경우)를 함께 계산해주기 위해 team 배열의 값이 1일 때를 스타트 팀일 때, 링크 팀일 때로 나누어 2가지 경우로 계산해주었습니다.

.

평소 문제의 입력 범위가 작으면 재귀함수로 풀어버리려는 습관(?)이 있어서

이번에도 재귀함수로 먼저 접근해보았습니다.

하지만 문제를 풀면서도 뭔가 더 쉽고 간단하게 풀 수 있는 방법이 있을 것이라는 생각이 들더라구요 ㅜ

그래서 다음번에는 이 문제를 좀 더 가볍게? 더 빠르게 만들어보려고 합니다 ㅎ..

to be continued...☆