백준 14889. 스타트와 링크

알고리즘 기초 문제 중 브루트포스-재귀 문제(530)

스타트와 링크

1. 간단 설명

N명의 사람들을 N/2명씩 나누어 팀을 생성한다

그런데 각 팀원별로 시너지가 있어서 1번이 2번이 만나면 S_12만큼의 전력을 낼 수 있다

2번이 1번과 만나면 S_21만큼 낼 수 있다

즉, 1번과 2번이 같은팀이면 S_12, S_21 만큼의 전력을 낼 수 있음

이런식으로 팀원을 뽑을 때, 각 팀의 전력차를 구해서 최소가 되도록 하는 문제

2. 예시

스타트 팀에 1, 2번을 뽑으면, S_12 + S_21 = 1 + 4 = 5

링크 팀에 3, 4번을 뽑으면, S_34 + S_43 = 2 + 5 = 7 이므로

전력차는 2가 난다

스타트팀에 1, 4, 링크 팀에 2, 3을 뽑으면

S_14 + S_41 = 3 + 3 = 6

S_23 + S_32 = 5 + 1 = 6 이므로

전력차는 0이 나므로 최소 전력차는 0이 된다

근데 사이좋게 못하는거 아닌가??

3. 알고리즘

1. N과 S값들 입력받기
2. N_C_(N/2)를 뽑아 start_team 생성
2. 뽑히지 않은 사람들을 모아 link_team 생성
3. 각 팀의 포인트 계산
4. 두 포인트의 차를 계산하여 최소값 갱신
5. 최소값 출력

필요 변수들

• 사람 수 int N(4 ≤ N ≤ 20, N은 짝수)
• 배열 S[N][N] 각 원소는 100보다 작은 자연수
• 각 팀의 점수 start_point, link_point;
• 최소값 int min_diff
• 팀에 속해있는지 체크할 배열 bool used[N] : true라면 start_team, false라면 link_team

4. 소스코드

직접 구현한 조합 버전

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int N;
int s[21][21];
bool used[21];
vector<int> start_team, link_team;

int min_diff = 21e8;

// 각 팀의 포인트 계산
int PointCheck(vector<int>& start_team, vector<int>& link_team) {
	
	int start_point = 0, link_point = 0;

	// start_point = (1,2) + (1,3) + (1,4) + ... (2,3) + (2,4) + (3,4)
	for (int elem : start_team) {
		for (int i = 0; i < N; i++) {
			if(used[i]==true){
				start_point += s[elem][i];
			}
		}
	}
	
	for (int elem : link_team) {
		for (int i = 0; i < N; i++) {
			if (used[i] == false) {
				link_point += s[elem][i];
			}
		}
	}

	return abs(start_point - link_point);
}

// N명중 N/2명을 뽑는 조합. 
void combination(int level, int start) {
	if (level == N / 2) {
		// start_team에 뽑히지 않은 선수들 link_team에 넣기
		for (int i = 0; i < N; i++) {
			if (used[i] == false) {
				link_team.push_back(i);
			}
		}

		// 두 팀의 전력차이 계산
		min_diff = min(min_diff, PointCheck(start_team, link_team));

		link_team.clear(); // 계산 후 link_team을 초기화하여 다음 팀 생성을 할 수 있도록 함

		return;
	}

	for (int i = start; i < N; i++) {
		
		used[i] = 1; 
		start_team.push_back(i);

		combination(level + 1, i + 1);

		used[i] = 0;
		start_team.pop_back();
	}
}

int main() {
	// freopen_s(new FILE*, "input.txt", "r", stdin);
	cin >> N;
	for (int y = 0; y < N; y++){
		for (int x = 0; x < N; x++) {
			cin >> s[y][x];
		}
	}

	combination(0, 0);

	cout << min_diff;

	return 0;
}

메모리 절약을 위해 팀원의 벡터를 별도로 둘 필요 없이

used를 이용하여 팀을 구분했으므로

이를 이용해서 바로 계산해도 될것 같다

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int N;
int score[21][21];
vector<int> player;

int main() {
	// freopen_s(new FILE*, "input.txt", "r", stdin);
	cin >> N;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> score[i][j];
		}
	}

	// 선택된 선수는 1, 선택되지 않은 선수는 0으로 기록
	player.resize(N);
	for (int i = N/2; i < N; i++) {
		player[i] = 1;
	}

	int min_val = 21e8;
	do {
		int start_score = 0, link_score = 0;
		for (int i = 0; i < N; i++) {
			
			if (player[i] == 0) {
				for (int j = 0; j < N; j++) {
					if(player[j] == 0)
						start_score += score[i][j];
				}
			}
			
			else {
				for (int j = 0; j < N; j++) {
					if(player[j] == 1)
						link_score += score[i][j];
				}
			}
		}

		min_val = min(min_val, abs(start_score - link_score));

	} while (next_permutation(player.begin(), player.end()));

	cout << min_val;

	return 0;
}

next_permutation을 이용해 조합을 생성한 버전