[BOJ] 15661. 링크와 스타트

2개로 팀을 나눠서 답을 구하는 문제이다.

스타트와 링크 문제와는 다르게 정확히 두개의 팀이 같은 팀원수를 가지는 것이 아니라 다른 두개의 팀으로 나눠지기만 하면 되는 문제이다. 그래서 이문제를 비트마스킹으로 접근하였다. 비트 마스킹을 이용하여 예를 들면 N=4일때 0001 부터 1110 까지 수를 구하고 1과 0으로 팀을 나누어서 값을 구하여 비교해주는 방식으로 답을 구하였다.

package boj2;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
 
public class Main_bj_15661_링크와스타트 {
    
    static int [][] people;
    static int N;
    
    static int answer;
    static List<Integer> team1;
    static List<Integer> team2;
    
    public static void main(String[] args) throws Exception  {
        BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
        N=Integer.parseInt(br.readLine());
        
        people=new int[N][N];
        for(int i=0;i<N;i++) {
            st=new StringTokenizer(br.readLine());
            for(int j=0;j<N;j++) {
                people[i][j]=Integer.parseInt(st.nextToken());
            }
        }
        team1=new ArrayList<>();
        team2=new ArrayList<>();
        answer=Integer.MAX_VALUE;
        pickTeamWithBit();
        System.out.println(answer);
        
    }
    
    static void pickTeamWithBit(){
        for(int i=1;i<(1<<N)-1;i++) {
            
            for(int j=0;j<N;j++) {
                if((i & (1<<j))!=0) {    //해당 j번째 비트가 켜져있을 경우
                    team1.add(j);
                }else {                    //해당 j번째 비트가 꺼져있을 경우
                    team2.add(j);
                }
            }
            findAnswer();
            team1.clear();
            team2.clear();
        }
    }
    
    static void findAnswer() {
        int size1 =team1.size();
        int size2 =team2.size();
        
        int sum1=0;
        int sum2=0;
        
        for(int i=0;i<size1;i++) {
            for(int j=0;j<size1;j++) {
                if(i!=j) {
                    sum1+=people[team1.get(i)][team1.get(j)];
                }
            }
        }
        for(int i=0;i<size2;i++) {
            for(int j=0;j<size2;j++) {
                if(i!=j) {
                    sum2+=people[team2.get(i)][team2.get(j)];
                }
            }
        }
        
        answer=Math.min(answer, Math.abs(sum1-sum2));
        
    }
}