[BOJ_C] 14889번

#문제

BOJ 14889번 문제

#풀이

n명을 n/2명으로 구성된 2개의 팀으로 나눈 뒤, 각 팀의 두명씩 추출하여 능력치를 계산하고 그 차를 구한다. 즉, n명을 n/2로 나누고 2중 for문으로 중복되지 않게 visited를 이용하여 2명을 추출한다. 그 뒤 map[i][j]+map[j][i]를 통하여 팀의 능력치를 더하고 그 값들의 차를 구하면 된다.

#코드

 

#include <stdio.h>
#include <math.h> //절댓값을 구하기 위함

int N, MIN = 1000000;
int map[20][20];
int visited[20];

//cur = 선수 번호 / cnt = 팀원 수
void f(int cnt, int cur) {
	
	if (cnt == N / 2) {
		int start = 0, link = 0;
		
		//능력치 더하기
		for (int i = 0; i < N; i++) {
			for (int j = i + 1; j <= N; j++) {
				if (visited[i] == 1 && visited[j] == 1) {
					start += map[i][j];
					start += map[j][i];
				}
				else if(visited[i] == 0 && visited[j] == 0){
					link += map[i][j];
					link += map[j][i];
				}
			}
		}

		//능력치 최소값 구하기
		if (MIN > abs(start - link)) {
			MIN = abs(start - link);
		}

		return;
	}

	//다음 선수
	for (int i = cur; i < N; i++) {
		if (visited[i] != 1) {
			visited[i] = 1;
			f(cnt + 1, i);
			visited[i] = 0;
		}
	}

	return;
}

int main() {
	scanf_s("%d", &N);

	//map[][] 입력받기
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			scanf_s("%d", &map[i][j]);
		}
	}

	//f()함수 호출하기
	f(0, 0);

	//min 출력하기
	printf("%d", MIN);
	return 0;
}