BOJ_S2_14889

📁 [S2_14889] 스타트와 링크

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

 
public class Main {
	static int N;
	static int[][] arr;
	static boolean[] c;
	static int min = Integer.MAX_VALUE;
	static int res = 0;
	static List<Integer> team1;
	static List<Integer> team2;
	static int team1_sum;
	static int team2_sum;
	
	public static void main(String[] args) throws IOException{
		StringTokenizer st = null;
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		// 사람 수
		N = Integer.parseInt(br.readLine());
		
		arr = new int[N][N];
		
		// 뽑음 유무
		c = new boolean[N];
		
		// 입력
		for(int i=0; i<N; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			for(int j=0; j<N; j++) {
				arr[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		team1 = new ArrayList<Integer>();
		team2 = new ArrayList<Integer>();
		
		comb(0,0);
		System.out.println(min);
		
	}

	// 조합
	static void comb(int idx, int start) {
		
		if(idx == N/2) {			
			for(int i=0; i<N; i++) {
				if(c[i]) {
					team1.add(i);
				}
				else {
					team2.add(i);
				}
			}
			
			// team1 합구하기
			for(int i=0; i<team1.size(); i++) {
				for(int j=0; j<team1.size(); j++) {
					team1_sum += arr[team1.get(i)][team1.get(j)];
				}
			}
			
			// team2 합구하기
			for(int i=0; i<team2.size(); i++) {
				for(int j=0; j<team2.size(); j++) {
					team2_sum += arr[team2.get(i)][team2.get(j)];
				}
			}
			
			// 최솟값 구하기
			min = Math.min(min, Math.abs(team1_sum - team2_sum));
			// 둘다 초기화
			team1.clear();
			team2.clear();
			team1_sum = 0;
			team2_sum = 0;
			
			return;
		}
		
		for(int i=start;i<N; i++) {
			c[i] = true;
			comb(idx+1,i+1);
			c[i] = false;
		}
	}
}

🤔 나의 생각

이 문제는 순서 상관 없이 몇명을 뽑아서 팀을 이루는 조합 문제이다.
처음에 ij, ji 두 개의 합을 배열로 따로 뺄려고 생각했으나 딱히 좋은 아이디어는 아닌 것 같아 통과했다.
그리고 이제 N 명중에 N/2 명씩 뽑아서 boolean에 true로 저장했다.
true 된 애들은 start 팀 (team1) 로 칭했고 false 인 애들은 link 팀 (team2) 로 칭했다.
뽑아서 그 idx를 list에 저장해서 그 idx 값을 가지고 배열에 접근해 값을 더해주었다.
그리고 두 팀 각각의 선수들의 총 합을 뺀 결과가 가장 작은 값을 출력해주었다.
조합을 알고 있으면 어렵지 않은데 idx를 빼오고 더해주고 이 작업이 좀 생각이 필요했던 것 같다.