백준 15661 - 링크와 스타트

Java

15661 번 - 링크와 스타트

문제

접근 방법

코드

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

public class Main {
	static int n, result = Integer.MAX_VALUE;
	static int[][] stat;
	static int[] link, start;
	static boolean[] vis;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer stk;
    	n = stoi(br.readLine());
    	stat = new int[n][n];
    	vis = new boolean[n];

    	for(int i = 0; i < n; i++) {
    		stk = new StringTokenizer(br.readLine());
    		for(int j = 0; j < n; j++) {
    			stat[i][j] = stoi(stk.nextToken());
    		}
    	}
		// 인원수 제한 없이 두 팀으로 나누므로, 인원을 나눌 수 있는 모든 경우를 확인
    	for(int lim = 2; lim <= n / 2; lim++) {
    		link = new int[lim];
    		start = new int[n - lim];
    		DFS(0, lim, 0);
    	}

    	System.out.println(result);

    	br.close();
	}
	// 한 팀의 사람 수 만큼 조합으로 뽑는다.
	private static void DFS(int lv, int lim, int st) {
		if(lv == lim) {
			int rt = getDiff(lim);
			result = Math.min(result, rt);
			return;
		}
		for(int i = st; i < n; i++) {
			vis[i] = true;
			DFS(lv + 1, lim, i + 1);
			vis[i] = false;
		}
	}
	// 2 팀으로 인원을 나눈다
	private static int getDiff(int lim) {
		int lIdx = 0, sIdx = 0;
		int lLen = lim, sLen = n - lim;
		// 뽑은 사람은 해당 인덱스에 true로 들어가 있다
		for(int i = 0; i < n; i++) {
			if(vis[i]) {
				link[lIdx] = i;
				lIdx++;
			}
			else {
				start[sIdx] = i;
				sIdx++;
			}
		}

		int linkStat = getStat(link, lLen);
		int startStat = getStat(start, sLen);

		return Math.abs(linkStat - startStat);
	}
	// 각 팀의 능력치 합을 구한다
	private static int getStat(int[] arr, int len) {

		int sum = 0, y,x;
		for(int i = 0; i < len; i++) {
			for(int j = 0; j < len; j++) {
				if(i == j)
					continue;
				y = arr[i];
				x = arr[j];
				sum += stat[y][x];
			}
		}

		return sum;
	}

	static int stoi(String str) {
    	return Integer.parseInt(str);
    }
}

조금 더 개선된 버전

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

public class Main {
	static int n, result = Integer.MAX_VALUE;
	static int[][] stat;
	static boolean[] vis;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer stk;
    	n = stoi(br.readLine());
    	stat = new int[n][n];
    	vis = new boolean[n];

    	for(int i = 0; i < n; i++) {
    		stk = new StringTokenizer(br.readLine());
    		for(int j = 0; j < n; j++) {
    			stat[i][j] = stoi(stk.nextToken());
    		}
    	}
    	for(int lim = 2; lim <= n / 2; lim++)
    		DFS(0, lim, 0);

    	System.out.println(result);
    	br.close();
	}

	private static void DFS(int lv, int lim, int st) {
		if(lv == lim) {
			int link = 0;
			int start = 0;
			for(int i = 0; i < n; i++) {
				for(int j = 0; j < n; j++) {
					if(vis[i] && vis[j]) {
						link += stat[i][j];
					}
					if(!vis[i] && !vis[j])
						start += stat[i][j];
				}
			}
			result = Math.min(result, Math.abs(link - start));
			return;
		}
		for(int i = st; i < n; i++) {
			if(!vis[i]) {
				vis[i] = true;
				DFS(lv + 1, lim, i);
				vis[i] = false;
			}
		}
	}

	static int stoi(String str) {
    	return Integer.parseInt(str);
    }
}

총평

후기

개선할 점