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

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

14889번: 스타트와 링크

---

문제 풀이

 1. 능력치를 나타내는 2차원 배열 board에 값을 입력받고 팀원의 소속을 나타내는 배열 team을 초기화해준다.

 2. 입력받은 총 인원 n의 반만큼 set_teams로 팀을 나누어주고 맞게 떨어진다면 함수 get_ability_of_team을 호출한다.

 3. 함수 get_ability_of_team으로 나눠진 두 팀의 능력치를 연산하고, 뺀 값을 반환한다.

 

  <함수 : set_teams>

중복 없이 n의 반의 크기인 팀을 나누는 함수. 중복을 없애기 위해서 이전 idx + 1 만큼의 값을 재귀 호출 시 매개변수로 가져간다. 팀이 나누어졌다면 함수 get_ability_of_team를 호출해서 값을 연산한다. 최솟값과 찾아 mymin에 저장한다.

  <함수 : get_ability_of_team>

함수 set_teams로 분리된 각 팀의 능력치를 연산하는 함수. 불린 배열 team으로 start팀과 link팀을 나눠진 팀을 구분한다. 배열 team의 값이 모두 참이거나 거짓이면 각 팀의 총합에 더하고 각 총합을 뺀 값을 리턴한다. 특히 모두 거짓이여야하기 때문에 else if를 써줘야한다.

느낀 점

 백트래킹의 마지막 문제였는데 생각보다 그렇게 어렵진 않았다. 구현까지는 괜찮았는데 피곤해서 '+=' 를 제대로 못 써서 잠깐 애를 먹었다. 마지막에 살짝 애 먹은 것 빼고는 계속 스무스했다.

코드

#include <iostream>
using namespace std;

int n; 
int board[20][20] = { 0, };
bool team[20] = { 0, };
int mymin = 20001;
int result = 0;

int get_ability_of_team(int n) {
	int sum1 = 0, sum2 = 0;
	for (int i = 0; i < n - 1; i++) {
		for (int j = i + 1; j < n;j++) {
			if (team[i] && team[j])
				sum1 += board[i][j] + board[j][i];
			else if (!team[i] && !team[j])
				sum2 += board[i][j] + board[j][i];
		}
	}
	return abs(sum1 - sum2);
}

void set_teams(int cnt, int idx) {
	if (cnt == n/2) {
		result = get_ability_of_team(n);
		if (mymin > result) mymin = result;
		return;
	}
	for (int i = idx; i < n; i++) {
		if (team[i]) continue;
		team[i] = true;
		set_teams(cnt + 1, i+1);
		team[i] = false;
	}
}

int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n;j++) {
			cin >> board[i][j];
		}
		team[i] = false;
	}
	set_teams(0, 0);
	cout << mymin;
}