< 백준 BaekJoon : 14889번 스타트와 링크 > C++

<< 문제 >>

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

14889번: 스타트와 링크

 

이것도 next_permutation()을 이용하면 쉽게 활용할 수 있다. 

 

vector에 사람 수의 절반만큼 0, 또 절반만큼 1을 넣고 next_permutation을 돌리면 모든 경우의 팀 선정을 볼 수 있다.  

 

이를 이용해서 모든 조합을 다 더해보면 알 수 있다.

 

<< 코드 >> 

#include <iostream>
#include<vector>
#include <algorithm>
using namespace std;



int main() {
	int num;
	cin >> num;
	
	// 둘이 합쳐진 능력치
	vector<vector<int>> abilityTable;
	for (int i = 0; i < num; i++) {
		vector<int> tempVec;
		abilityTable.push_back(tempVec);
		for (int j = 0; j < num; j++) {
			int temp;
			cin >> temp;
			abilityTable[i].push_back(temp);
		}
	}
	// 팀 0과 1로 구분
	vector<int> manList;
	for (int i = 0; i < num / 2; i++) {
		manList.push_back(0);
	}
	for (int i = num/2; i < num ; i++) {
		manList.push_back(1);
	}

	vector<int> teamStart;
	vector<int> teamLink;

	int sumTeamStart;
	int sumTeamLink;
	int min = 2000000000;
	int diff;
	do {
		

		sumTeamStart = 0;
		sumTeamLink = 0;

		teamStart.clear();
		teamLink.clear();

		// 사람마다의 번호 (0~num-1)을 각 팀 vector에 배분
		for (int i = 0; i < manList.size(); i++) {
			if (manList[i] == 0) {
				teamStart.push_back(i);
			}
			else {
				teamLink.push_back(i);
			}
		}	

		// 각 팀의 조합을 점수로 판별
		for (int i = 0; i < num/2; i++) {
			for (int k = i + 1; k < num / 2; k++) {
				sumTeamStart += abilityTable[teamStart[i]][teamStart[k]];
				sumTeamStart += abilityTable[teamStart[k]][teamStart[i]];
			}
		}
		for (int i = 0; i < num / 2; i++) {
			for (int k = i + 1; k < num / 2; k++) {
				sumTeamLink += abilityTable[teamLink[i]][teamLink[k]];
				sumTeamLink += abilityTable[teamLink[k]][teamLink[i]];
			}
		}

		diff = abs(sumTeamLink - sumTeamStart);
		if (diff < min) {
			min = diff;
		}
	}
	while(next_permutation(manList.begin(), manList.end()));

	cout << min;
}

 

 

 

<< 깃헙 >>

https://github.com/J2on/StudyAlgorithm_Part2/tree/main/%EB%B0%B1%EC%A4%80/Silver/14889.%E2%80%85%EC%8A%A4%ED%83%80%ED%8A%B8%EC%99%80%E2%80%85%EB%A7%81%ED%81%AC