백준 14889 스타트와 링크

백준 14889 스타트와링크

구현 전 생각

순서가 상관 없기 떄문에 조합으로 3가지를 뽑고 isSelected 배열을 이용해서 뽑힌 숫자와 안뽑힌 숫자를 나누어서 팀을 나누고 123 456 인경우 1의 2,3인덱스를 더하고 2의 1,3 인덱스를 더하고 3의 1,2인덱스를 더하는 방법으로 더해서 최솟값을 찾아서 갱신하는 방법

아쉬운점

없다 생각한대로 해결한 문제!

코드

package com.study29;

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

import javax.swing.InputMap;

public class backjoon_14889_스타트와링크 {
	static int map[][];
	static int R,N;
	static boolean[] isSelected;
	static int[] start,link;
	static int min;
	public static void main(String[] args) throws NumberFormatException, IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		map = new int[N][N];
		isSelected = new boolean[N];
		R=N/2;
		start = new int[R];
		link = new int[R];
		min=999999;
		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());
			}
		}
		combination(0,0);
		System.out.println(min);
		
	}
	public static void combination(int cnt,int target) {	
		//조합의 개수가 n/2 즉 R개가 되는 순간 start와 link팀으로 나눈다.
		if(target==R) {
			int Scnt=0;
			int Lcnt=0;
			for (int i = 0; i < N; i++) {
				if(isSelected[i]) {
					start[Scnt++]=i;
					continue;
				}
				
				link[Lcnt++]=i;
			}
			min = Math.min(min, sum());
			return;
		}
		if(cnt ==N) {
			return;
		}
		if(isSelected[cnt]) return;
		isSelected[cnt]=true;
		//선택한 경우
		combination(cnt+1, target+1);
		isSelected[cnt]=false;
		//선택하지 않은경우
		combination(cnt+1, target);
	}
	
	public static int sum() {
		int Ssum=0; //스타트팀의 합
		int Lsum=0; //링크팀의 합
		for (int i = 0; i < R; i++) {
			for (int j = 0; j < R; j++) {
				if(i==j) continue;
				Ssum+=map[start[i]][start[j]];
				Lsum+=map[link[i]][link[j]];
			}
		}
		return Math.abs(Ssum-Lsum); //둘의 차를 절대값으로 
	}

}