링크와 스타트(백준 15661번)☆

sw expert academy의 요리사 (4012와 유사함)

 

15661번: 링크와 스타트 (acmicpc.net)

15661번: 링크와 스타트

import java.util.Arrays;
import java.util.Scanner;

public class Main {

	static int N;
	static int[][]S;
	static boolean[] visit;
	static int answer=Integer.MAX_VALUE;
	
	public static void main(String[] args) {
		
		Scanner sc=new Scanner(System.in);
		N=sc.nextInt();
		S=new int[N+1][N+1];
		
		for(int i=1;i<=N;i++) {
			for(int j=1;j<=N;j++) {
				S[i][j]=sc.nextInt();
			}
		}
		
		visit=new boolean[N+1];
		
		for(int i=1;i<=N/2;i++) { //횟수
			for(int j=1;j<=N;j++) { //시작 인덱스 
				visit[j]=true;
				solution(j,1,i);
				visit[j]=false;
			}
			
			
		}
		System.out.println(answer);
	}
	
	static void solution(int i, int cnt, int count) {
		
		if(cnt==count) { 
			//차이 확인
			answer=Math.min(answer, count(cnt));
			return;
			
		}
		
		for(int j=i+1;j<=N;j++) {
			if(!visit[j]) {
				visit[j]=true;
				solution(j,cnt+1, count);
				visit[j]=false;
			}
		
		}
		
		
	}
	
	static int count(int t) { //true의 개수
		int f=N-t;
		
		int t_sum=0;
		int f_sum=0;
		
		//true 팀
		if(t==1)  t_sum=0;
		else {
			for(int i=1;i<=N;i++) {
				if(!visit[i]) continue;
				for(int j=1;j<=N;j++) {
					if(visit[j]) t_sum+=S[i][j];
				}
			}
		}
		if(f==1) f_sum=0;
		else {
			for(int i=1;i<=N;i++) {
				if(visit[i]) continue;
				for(int j=1;j<=N;j++) {
					if(!visit[j]) f_sum+=S[i][j];
				}
			}
		}
		
		return Math.abs(f_sum- t_sum);
	}

}