백준 15661. 링크와 스타트

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

링크와 스타트

1. 간단 설명

이전 문제 스타트와 링크와 유사하지만 한가지 조건만 변경되는 문제

N명의 사람들을 그냥 나누어 팀을 생성한다

즉, N/2로 나누는게 아니라

4명을 1:3으로도 나눌 수 도 있는 상황

이걸 더이상 축구라고 할 수 있을까

2. 예시

6
0 6 1 2 3 4
6 0 5 6 7 8
9 10 0 1 1 1
11 12 1 0 1 1
13 14 1 1 0 1
15 16 1 1 1 0

다음과 같이 주어졌을 때

(1, 2) (3, 4, 5, 6) 으로 나누면 0으로 값이 최소화 된다

3. 알고리즘

1. N과 S값들 입력받기
2. 1명, 2명, ... N-1명씩 뽑아 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;

	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);
}

void combination(int level, int start, int limit) {
	if (level == limit) {
		// 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은 clear해줘야함

		return;
	}

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

		combination(level + 1, i + 1, limit);

		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];
		}
	}

	/*****이부분이 수정됨. 몇명을 뽑을지 조합의 매개변수로 넘겨줌*****/
	for (int limit = 1; limit < N; limit++) {
		combination(0, 0, limit);
	}

	cout << min_diff;

	return 0;
}