백준 14889번 _ 스타트와 링크

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

14889번: 스타트와 링크

풀이방법

이 문제도 조합을 이용하면 매우매우 간단하다.

 

1. 조합을 이용해서 팀1, 팀2로 나눈다

2. 나눈 팀의 스코어를 계산한다.

3. 절대값(팀1 -팀2)과 저장된 값과 최솟값을 비교한다.

4. 모든 조합이 나올때까지 반복 (만약 지금 저장된 값이 0이면 0보다 최솟값은 없으므로 break해도됨)

---

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

#define LIMIT 987654321 

using namespace std;
int N;
int S[21][21];

void Input()
{
	cin >> N;
	int value;
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			cin >> value;
			S[i][j] = value;
		}
	}
}

int calculate(const vector<int>& team)
{
	int teamScore= 0;
	for (int i = 0; i < (int)team.size(); i++)
	{
		int first = team[i];
		for (int j = i + 1; j < (int)team.size(); j++)
		{
			int second = team[j];
			teamScore += (S[first][second] + S[second][first]);
		}
	}
	return teamScore;
}

void solve()
{
	int minValue = LIMIT;
	//0번팀과 1번팀으로 나누겠음
	vector<int>team;
	team.resize(N, 0);
	for (int i = 0; i < (N/2); i++)
		team[i] = 1;
	
	sort(begin(team), end(team));

	do
	{
		//divide team
		vector<int>firstTeam;
		vector<int>secondTeam;
		for (int i = 0; i < N; i++)
		{
			if (team[i] == 0)
				firstTeam.push_back(i);
			else
				secondTeam.push_back(i);
		}

		//calculate
		minValue = min(minValue, abs((calculate(firstTeam) - calculate(secondTeam))));

		//이때는 더 할 필요가 없음
		if (minValue == 0)
			break;

	} while (next_permutation(begin(team), end(team)));

	cout << minValue;
}

int main()
{
	Input();
	solve();
	return 0;
}

---

후기

next_permutation 정말 좋다. 단점이 하나있다면 조합이나 순열 나오면 이 함수만 써대서 순열, 조합 어떻게짰는지 기억나지도 않는다ㅋㅋㅋ