백준 14889번: 스타트와 링크 - DFS, 백트래킹, 조합 C++

https://www.acmicpc.net/problem/14889

14889번: 스타트와 링크

1.문제설명

N명이 있을 때 N/2로 각각 팀을 나눠주고

문제에서 주어진 점수표로 각각 팀의 점수를 계산해

차이가 최소가 되도록 구해주어야한다.

 

 

2.접근방법[알고리즘]

2-1. 팀 나누기

DFS를 돌면서 조합으로 n명중 n/2명을 뽑아준다.

 

bool 타입 배열 ch에 뽑힌 번호는 true 안 뽑힌 번호는 false로 지정해줘서 두 팀으로 나눠줄 수 있다.

 

두 팀으로 나눠준 후 점수를 구해준다.

void DFS(int cur, int L) {
	if (L == n / 2) {
		ans = min(ans, cal());
	}
	else {
		for (int i = cur+1; i <= n; i++) {
			ch[i] = true;
			DFS(i, L + 1);
			ch[i] = false;
		}
	}
}

 

 

2-2. 점수구하기

int cal() {
	int point1=0, point2=0;
	for (int i = 1; i <= n; i++){
		for (int j = 1; j <= n; j++){
			if (ch[i] == true && ch[j] == true) 
				point1 += arr[i][j];
			if (ch[i] == false && ch[j] == false) 
				point2 += arr[i][j];
		}
	}
	return abs(point1 - point2);
}

만약 1과 2가 한팀이라고 가정하면

그 팀의 점수는 arr[1][2] + arr[2][1]이다.

 

만약 1, 2, 3이 한팀이라면

arr[1][2] + arr[1][3] + arr[2][1] + arr[2][3] + arr[3][1] + arr[3][2]

이렇게 된다.

 

참고로 문제에서 arr[i][i] = 0 으로 주기 때문에

arr[1][2] + arr[1][3] + arr[2][1] + arr[2][3] + arr[3][1] + arr[3][2]는

arr[1][1] + arr[1][2] + arr[1][3] + arr[2][1] + arr[2][2] + arr[2][3] + arr[3][1] + arr[3][2] + arr[3][3]과 동일하다.

그래서 위 코드처럼 하면 각 팀의 점수를 구해줄 수 있다.

 

점수를 구하는 과정도 DFS로 순열을 구현해서 할 수 있겠으나 

귀찮기도하고 이문제에서는 원소가 두개로 지정되어있으므로 for문으로 구현하는게 편하다.

 

 

3. 문제풀이코드 C++

#include <bits/stdc++.h>
using namespace std;

int arr[22][22], n, ans=INT_MAX;
bool ch[22];

//팀별 점수 계산해주는 함수 
int cal() {
	int point1=0, point2=0;
	for (int i = 1; i <= n; i++){
		for (int j = 1; j <= n; j++){
			if (ch[i] == true && ch[j] == true) 
				point1 += arr[i][j];
			if (ch[i] == false && ch[j] == false) 
				point2 += arr[i][j];
		}
	}
	return abs(point1 - point2);
}


//조합으로 팀 나눠주는 함수 
void DFS(int cur, int L) {
	if (L == n / 2) {
		ans = min(ans, cal());
	}
	else {
		for (int i = cur+1; i <= n; i++) {
			ch[i] = true;
			DFS(i, L + 1);
			ch[i] = false;
		}
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cin >> arr[i][j];
		}
	}

	DFS(0, 0);

	cout << ans;
}

백준 14889번 메모리, 시간