[BOJ] 14889번 : 스타트와 링크

1. problem : 

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

 

2. solution 1 :

#include <bits/stdc++.h>
using namespace std;
int n;
int board[22][22]; 
bool isused[12];
vector<int> star; 
vector<int> link; 
int ans = 0x7f7f7f7f;
int synergy_sum(vector<int>& v) {
	int syn_sum = 0;
	for (int i = 0; i < v.size(); i++) {
		for (int j = 0; j < v.size(); j++) {
			if (i == j) continue; 
			syn_sum += board[v[i]][v[j]];
		}
	}
	return syn_sum;
}

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n; 

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) cin >> board[i][j]; 
	}

	vector<int> boj(n,1); 
	fill(boj.begin(), boj.begin() + n / 2, 0); 
	do {
		int diff = 0;
		for (int i = 0; i < n; i++) {
			if (boj[i] == 0) star.push_back(i); // star팀
			else link.push_back(i); // link팀 
		}
		diff = abs(synergy_sum(star) - synergy_sum(link)); 
		ans = min(ans, diff);
		for (int i = 0; i < n / 2; i++) { // start link 초기화
			star.pop_back();
			link.pop_back();
		}
	} while (next_permutation(boj.begin(), boj.end()));

	cout << ans << '\n';
}

 

3. solution 2 :

// Authored by : sukam09
// Co-authored by : BaaaaaaaaaaarkingDog
// http://boj.kr/a75486aadfc04beeb40786a0728ffc78
#include <bits/stdc++.h>
using namespace std;

int n;
int a[25][25];

int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);

  cin >> n;
  for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++) cin >> a[i][j];

  vector<int> team(n);
  fill(team.begin() + n / 2, team.end(), 1);
  int ans = 0x7f7f7f7f;
  // team = {0, 0, 0, .., 0, 1, 1, .. ,1}, team[i]는 i번째 선수의 팀을 의미
  do {
    int diff = 0; // 능력치의 차이
    for (int i = 0; i < n; i++) {
      for (int j = i+1; j < n; j++){
        if(team[i] != team[j]) continue;
        if(team[i] == 0) diff += (a[i][j] + a[j][i]);
        else diff -= (a[i][j] + a[j][i]);
      }
    }
    ans = min(ans, abs(diff));    
  } while (next_permutation(team.begin(), team.end()));
  cout << ans;
}

source code 출처 : https://github.com/encrypted-def/basic-algo-lecture/blob/master/0x0D/solutions/14889.cpp

basic-algo-lecture/0x0D/solutions/14889.cpp at master · encrypted-def/basic-algo-lecture