[백준 14889] 스타트와 링크

 

[문제 바로가기]

14889번: 스타트와 링크

 

💡풀이💡

1. 스타트 팀과 링크 팀을 나누는 모든 경우의 수 찾기 > 조합!

2. 모든 팀의 경우의 수를 돌면서 두 팀의 능력치의 차의 최솟값 구하기

 

 

1. 입력 값 저장하기

팀의 능력치는 Sij + Sji로 구하기 때문에 각 사람의 능력치를 2차원 배열로 저장했다.

같은 팀인지 아닌지를 저장하기 위해 N만큼의 크기를 가진 boolean 타입의 배열을 생성했다.

static int N = 0;
static boolean[] isTeam;
static int[][] power;


public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    N = Integer.parseInt(br.readLine());
    power = new int[N][N];

    for(int i=0; i<N; i++) {
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int j=0; j<N; j++) {
            power[i][j] = Integer.parseInt(st.nextToken());
        }
    }
    
    isTeam = new boolean[N];
}

 

 

2. 나눌 수 있는 모든 팀 구하기

N명의 사람을 N/2명씩 두 팀으로 나눴을 때 구할 수 있는 모든 팀은 N개에서 2개를 뽑는 조합과 동일하다.

1) 각 선수가 팀에 속해 있지 않으면

2) 선수를 팀에 넣고

3) 아직 속해 있지 않은 선수들을 한 팀에 N/2명 될 때까지 차례로 한 명씩 모두 넣는다.

public static void comb(int cnt, int start) {
	if(cnt == N/2) { // 팀이 완성 되면
		//각 팀의 능력치 계산하기
		return;
	}
		
	for(int i=start; i<N; i++) {
		if(!isTeam[i]) { // 1)
			isTeam[i] = true; // 2) 
			comb(cnt+1, i+1); // 3)
			isTeam[i] = false; 
		}
	}
}

 

 

3. 두 팀의 능력치의 차의 최솟값 구하기

isTeam()에서 같은 값을 가진 번호끼리 같은 팀이기 때문에 같은 값을 가진 선수들의 번호로 팀의 능력치를 구한다.

public static int calTeamPower() {
	int teamStart = 0;
	int teamLink = 0;
		
	for(int i=0; i < N; i++) {
		for(int j=i+1; j<N; j++) {
			if(isTeam[i] && isTeam[j]) teamStart += power[i][j] + power[j][i];
			if(!isTeam[i] && !isTeam[j]) teamLink += power[i][j] + power[j][i];
		}
	}
		
	int cal = Math.abs(teamStart - teamLink);
	return Math.min(min, cal);
}

 

 

 

4. 전체 코드

import java.io.*;
import java.util.*;

public class Main {
	static int N = 0;
	static boolean[] isTeam;
	static int[][] power;
	static int min = 100;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		power = new int[N][N];
		
		for(int i=0; i<N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			for(int j=0; j<N; j++) {
				power[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		isTeam = new boolean[N];
		comb(0,0);
		
		System.out.println(min);
	}
	
	public static void comb(int start, int cnt) {
		if(cnt == N/2) {
			//각 팀의 능력치 계산하기
			min = calTeamPower();
			return;
		}
		
		for(int i=start; i<N; i++) {
			if(!isTeam[i]) {
				isTeam[i] = true;
				comb(i+1, cnt+1);
				isTeam[i] = false;
			}
		}
	}
	
	public static int calTeamPower() {
		int teamStart = 0;
		int teamLink = 0;
		
		for(int i=0; i < N; i++) {
			for(int j=i+1; j<N; j++) {
				if(isTeam[i] && isTeam[j]) teamStart += power[i][j] + power[j][i];
				if(!isTeam[i] && !isTeam[j]) teamLink += power[i][j] + power[j][i];
			}
		}
		
		int cal = Math.abs(teamStart - teamLink);
		return Math.min(min, cal);
	}
	
}