백준 14889 <스타트와 링크>

 

일반적인 조합 문제이다 최대 20 C 10 이기 때문에 184756번이고 10명의 팀원을 각각 값을 계산해도 100이므로 184765*10 하고 두 팀이니 x2 해서 400만이 되지 않기 때문에 시간 내에 무사히 통과할 수 있는 문제이다.

 

삼성 A형 테스트 치고는 접근하는 방향도 생각하기도 쉬웠던 문제이다.

 

20명의 사람 중 절반을 나누는 조합이 부분이다.

 

find 함수에서는 a팀에 속하지 않은 사람들을 b의 배열에 넣고 각각의 사람들을 기준으로 팀의 능력치를 구하고 난 뒤 두 점수의 최소 차이를 구한다.

 

 visit 함수를 이용해서 a팀에 속해있는 인원을 1로 만들어주고 차후에 a팀을 제외한 인원을 b팀에 넣어준 코드이다.

 

그 후에는 간단하게 각팀의 능력치를 계산해줘서 최소를 대입해주면 끝나는 간단한 문제이다.

 

삼성 역량테스트 중에서는 쉬운 문제에 속하고 이전에는 조합을 이용한 문제가 많이 나왔던 것 같다.

 

전체 코드

import java.util.Scanner;

public class Main{

	static int[][] map;
	static int n, min = 1000000000;
	static int[] a, b;

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner kb = new Scanner(System.in);
		n = kb.nextInt();
		map = new int[n][n];
		a = new int[n / 2];
		b = new int[n / 2];
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				map[i][j] = kb.nextInt();
			}
		}
		kb.close();
		find_min(0,0);
		System.out.print(min);
	}

	public static void find_min(int k,int where) {
		if (where == n / 2) {
			find();
			return;
		}
		if(k==n)
			return;
		a[where] = k;
		find_min(k+1,where+1);
		find_min(k + 1,where);
		
	}

	public static void find() {	
		int result1 =0;
		int result2=0;	
		int visit[]=new int[n];
        for(int i=0;i<n/2;i++){
            visit[a[i]]=1;
        }
        int count=0;
        for(int i=0;i<n;i++){
            if(visit[i]==0){
                b[count++]=i;
            }
        }
        
		for (int i = 0; i < n / 2 ; i++) {
			for (int j = i; j < n / 2; j++) {
				result1 += map[a[i]][a[j]]+map[a[j]][a[i]];
				
			}
		}
		for (int i = 0; i < n / 2 ; i++) {
			for (int j = i; j < n / 2; j++) {
				result2 += map[b[i]][b[j]]+map[b[j]][b[i]];
			}
		}
		result1 = Math.abs(result1 - result2);
		
		if (min > result1) {
			min =result1;
		}
	}

}