BOJ 14889번: 스타트와 링크

문제

문제 바로가기> BOJ 14889번: 스타트와 링크

14889번: 스타트와 링크

 

풀이

start와 link 팀을 나눌 수 있는 모든 경우의 수로 나누어주고, 두 팀의 능력치 차이의 최솟값을 구해주었다.

 

C++

#include<iostream>
#include<vector>
#define MAX 21
#define INF 1000000001
using namespace std;

int N, ans = INF;
int score[MAX][MAX];
bool start_team[MAX];

void input() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) cin >> score[i][j];
	}
}

void solution(int idx, int cnt) {
	if (cnt == N / 2) {
		int start = 0, link = 0;
		for (int i = 0; i < N; i++) {
			for (int j = i + 1; j < N; j++) {
				if (start_team[i] == start_team[j]) {
					if (start_team[i]) start += (score[i][j] + score[j][i]);
					else link += (score[i][j] + score[j][i]);
				}
			}
		}
		ans = min(ans, abs(start - link));
		return;
	}
	for (int i = idx; i < N; i++) {
		start_team[i] = true;
		solution(i + 1, cnt + 1);
		start_team[i] = false;
	}
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	input();
	solution(0, 0);
	cout << ans;
}

 

Java

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	
	static int N, ans=Integer.MAX_VALUE;
	static int[][] score;
	static boolean[] start_team;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		score = new int[N][N];
		start_team = new boolean[N];
		
		for(int i=0; i<N; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0; j<N; j++) {
				score[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		solution(0, 0);
		System.out.println(ans);
	}

	private static void solution(int idx, int cnt) {
		if (cnt == N / 2) {
			int start = 0, link = 0;
			for (int i = 0; i < N; i++) {
				for (int j = i + 1; j < N; j++) {
					if (start_team[i] == start_team[j]) {
						if (start_team[i]) start += (score[i][j] + score[j][i]);
						else link += (score[i][j] + score[j][i]);
					}
				}
			}
			ans = Math.min(ans, Math.abs(start - link));
			return;
		}
		for (int i = idx; i < N; i++) {
			start_team[i] = true;
			solution(i + 1, cnt + 1);
			start_team[i] = false;
		}
	}
}