Baekjoon14889: 스타트와 링크

스타트와 링크

2 초

512 MB

49286

24988

14525

47.398%

문제

오늘은 스타트링크에 다니는 사람들이 모여서 축구를 해보려고 한다. 축구는 평일 오후에 하고 의무 참석도 아니다. 축구를 하기 위해 모인 사람은 총 N명이고 신기하게도 N은 짝수이다. 이제 N/2명으로 이루어진 스타트 팀과 링크 팀으로 사람들을 나눠야 한다.

BOJ를 운영하는 회사 답게 사람에게 번호를 1부터 N까지로 배정했고, 아래와 같은 능력치를 조사했다. 능력치 Sij는 i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치이다. 팀의 능력치는 팀에 속한 모든 쌍의 능력치 Sij의 합이다. Sij는 Sji와 다를 수도 있으며, i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치는 Sij와 Sji이다.

N=4이고, S가 아래와 같은 경우를 살펴보자.

예를 들어, 1, 2번이 스타트 팀, 3, 4번이 링크 팀에 속한 경우에 두 팀의 능력치는 아래와 같다.

• 스타트 팀: S12 + S21 = 1 + 4 = 5
• 링크 팀: S34 + S43 = 2 + 5 = 7

1, 3번이 스타트 팀, 2, 4번이 링크 팀에 속하면, 두 팀의 능력치는 아래와 같다.

• 스타트 팀: S13 + S31 = 2 + 7 = 9
• 링크 팀: S24 + S42 = 6 + 4 = 10

축구를 재미있게 하기 위해서 스타트 팀의 능력치와 링크 팀의 능력치의 차이를 최소로 하려고 한다. 위의 예제와 같은 경우에는 1, 4번이 스타트 팀, 2, 3번 팀이 링크 팀에 속하면 스타트 팀의 능력치는 6, 링크 팀의 능력치는 6이 되어서 차이가 0이 되고 이 값이 최소이다.

입력

첫째 줄에 N(4 ≤ N ≤ 20, N은 짝수)이 주어진다. 둘째 줄부터 N개의 줄에 S가 주어진다. 각 줄은 N개의 수로 이루어져 있고, i번 줄의 j번째 수는 Sij 이다. Sii는 항상 0이고, 나머지 Sij는 1보다 크거나 같고, 100보다 작거나 같은 정수이다.

 

출력

첫째 줄에 스타트 팀과 링크 팀의 능력치의 차이의 최솟값을 출력한다.

 

풀이

점수 구하기 → 메소드

N은 항상 짝수, 20보다 같거나 작은 수이며 S의 값은 100보다 같거나 작다. 팀 시너지 점수(S)는 어떻게 나타낼 수 있을까?

팀을 4명이라고 하면 4x4 행렬이 주어질 것 이다.

4명÷2 = 2명의 팀의 시너지를 비교해야 한다.

	1	2	3	4
1
2
3
4

위에서 {1, 3} {2, 4}가 서로 팀이면 {1, 3}팀의 점수를 나타내면 다음과 같다.

1과 3에서 줄을 그은 교차점들을 모두 더하면 S의 합을 구할 수 있다

선수번호가 a, b, c라면 [선수번호][선수번호] 에 해당하는 index값을 모두 더하도록 메소드를 만든다.

 

뽑는 방법

4명이면 팀을 뽑는 가지수는 어떻게 될까? 순열을 사용해 4C2 = 4X3/2 = 6 라고 생각할 수 있지만,

나열해보면 {1,2} {1,3} {1,4} / {2,3} {2,4} {3,4}로 한쪽이 선택되면 나머지는 자동 선택이 되어 팀 나누는 방법은 겹친다.

이렇게 되는 이유는 4명 중에 2명을 선택한다고 해서 나머지 2명은 버려지는게 아니기 때문이다.

팀을 뽑는 경우의 수

N명이 있을 때 두 팀으로 나누는 경우의 수는 (N-1)C(N/2 -1) 이다. 한 명을 미리 뽑고 그 사람과 팀하고 싶은 N/2 - 1명을 뽑는 것이다.

6명이라면 팀을 나누는 경우의 수는 6C3이 아닌 5C2 = 5x4/2 = 10 이다

대표 세우기

N크기의 논리형 배열을 생성하면 모두 false 값을 가지고 있다.

여기서 1에게 먼저 true를 주고, 1과 같이 팀에 참여할 N/2 - 1명을 뽑는다

반복문

6명일 때 true를 O, false를 X로 나타내면

[ O , X, X, X, X ,X ] 에서 시작하는 것이다

팀을 만들 수 있는 방법은 X 5명 중 2명을 뽑는 경우의 수와 같다

[ O, O, O, X, X ,X ] [ O, O, X, O, X ,X ] [ O, O, X, X, O ,X ] [ O, O, X, X, X ,O ] [ O, X, O, O, X ,X ]

[ O, X, O, X, O ,X ] [ O, X, O, X, X ,O ] [ O, X, X, O, O ,X ] [ O, X, X, O, X ,O ] [ O, X, X, X, O ,O ]

배열의 1번 index부터 5번 index까지 순열의 방식으로 구하면 된다.

import java.util.*;
public class Main {
	static int N;
	static boolean[] team;
	static int[][] S;
	static int min=2000; //N=20, S=100이 최대므로 min 최대는 약 2000
	
    //두 팀의 차이를 구하고 최소값이면 값을 갱신
	static void getMin(){
		int sum = 0; //변수는 하나로 충분하다
		for(int i=0; i<N; i++) {
			for(int j=i+1; j<N; j++) {
            //i번째 사람과 j번째 사람이 모두 같은 팀일 때
				if(team[i] && team[j]) {
					sum+=S[i][j]+S[j][i];
            //배열에 기록된 시너지 점수 2개를 더해준다
				}else if(!team[i] && !team[j]) {
					sum-=S[i][j]+S[j][i];
				}
			}
		}
		min = Math.min(min, Math.abs(sum));
		if(min==0) { //값이 0이면 바로 출력한다
			System.out.print(0);
			System.exit(0);
		}
	}
	
	static void teamSelect(int start, int Depth){
	if(Depth==N/2-1) { //0번 index는 이미 선택했으므로 -1
		getMin();
		return;
	}
		for(int i=start;i<N;i++) {
			if(!team[i]) {
				team[i]=true;
				teamSelect(i+1,Depth+1);
                //겹치지 않게 선택하기 위해 i+1임을 주의
				team[i]=false;
			}
		}
	}
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		S = new int[N][N];
		team = new boolean[N];
		team[0]=true;
		for(int i=0; i<N; i++) {
			for(int j=0; j<N; j++) {
				S[i][j]=sc.nextInt();
			}
		}
		teamSelect(1,0);
        //파라미터를 두개 사용하는 이유는 중복을 막기 위해서이다
		System.out.print(min);
 }}

 

아무도 선택하지 않고 시작하는 경우

import java.util.*;
public class Main {
	static int N;
	static boolean[] team=new boolean[20];
	static int[][] S=new int[20][20];
	static int min=2000;
	static void getMin(){
		int sum = 0;
		for(int i=0; i<N; i++) {
			for(int j=i+1; j<N; j++) {
				if(team[i] && team[j]) {
					sum+=S[i][j]+S[j][i];
				}else if(!team[i] && !team[j]) {
					sum-=S[i][j]+S[j][i];}}}
		min = Math.min(min, Math.abs(sum));}
	static void teamSelect(int start, int Depth){
	if(Depth==N/2){
		getMin();
		return;}
		for(int i=start;i<N;i++) {
			if(!team[i]) {
				team[i]=true;
				teamSelect(i+1,Depth+1);
				team[i]=false; }}}
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		for(int i=0; i<N; i++) for(int j=0; j<N; j++)S[i][j]=sc.nextInt();	
		teamSelect(0,0);
		System.out.print(min);
 }}

*메모리를 더 사용하지만 코드를 더 짧게 만들 수 있다