BOJ 14889 스타트와 링크(JAVA) ⚽

문제 링크

14889번: 스타트와 링크

문제 설명

N개 중 절반을 조합으로 뽑아 두개의 그룹으로 나눠 그룹의 능력치 차이가 가장 적은 경우 구하기

입력

N: 총 인원수

Sij: i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치

Sji: j번 사람과 i번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치

Sij와 Sji는 다를 수도 있음, Sii는 항상 0

출력

그룹의 능력치 차이가 가장 적은 경우에서의 능력치 차이값

구조화

N개 중에 N/2개를 조합으로 뽑아 두 그룹으로 나눔

각 그룹별로 능력치를 구함

result는 능력치 차이값의 절대값에서 가장 작을 때로 업데이트

소스 코드

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

public class Main_14889_스타트와링크 {

	static int N, result = Integer.MAX_VALUE;
	static List<Integer> start;
	static List<Integer> link;
	static int[][] map;
	public static void main(String[] args) throws NumberFormatException, IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		N = Integer.parseInt(br.readLine());
		
		map = new int[N][N];
		
		for (int i = 0; i < N; i++) 
		{
			StringTokenizer st = new StringTokenizer(br.readLine());
			for (int j = 0; j < N; j++) 
			{
				map[i][j] = Integer.parseInt(st.nextToken());
			}	
		}
		
		// 조합
		combi(0,0,0);
		System.out.println(result);
	}
	private static void combi(int cnt, int s, int flag) {

		// 조합 완성
		if(cnt==(N/2))
		{
			start = new ArrayList<>();
			link = new ArrayList<>();
			
			for (int i = 0; i < N; i++) 
			{
				if((flag&(1<<i))!=0)
				{
					start.add(i);
				}
				else
				{
					link.add(i);
				}
			}
			int temp = Math.abs(calc(start)-calc(link));
			result = Math.min(temp, result);
			return;
		}
		
		for (int i = s; i < N; i++) 
		{
			combi(cnt+1, i+1,flag|(1<<i));
		}
	}
	
	private static int calc(List<Integer> list) {
		
		int sum = 0;
		for (int i = 0; i < list.size(); i++) 
		{
			for (int j = 0; j < list.size(); j++) 
			{
				if(i==j) continue;
				sum+=map[list.get(i)][list.get(j)];
			}
		}
		return sum;
	}

}