[백준] 14889 스타트와 링크

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

14889번: 스타트와 링크

 

문제

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

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

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

	1	2	3
4		5	6
7	1		2
3	4	5

예를 들어, 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이 되고 이 값이 최소이다.

 

 

 

내 풀이

 

 

나의 경우는 조합(Combination) 으로 나오는 팀이 나뉘는 경우의 수를 모두 찾아내보고

스타트 팀과 링크 팀의 구분이 유의미하다면 이렇게 나오지만 아닌 경우이기에 위의 3가지만 계산하면 된다 (개선할 점)

각 팀 내부에서 서로 나오는 시너지를 다시 위에서 사용했던 조합 알고리즘을 약간 변형하여 각 팀의 능력치를 계산합니다. 

둘의 차이를 기존의 최솟값과 비교하여 구하고자 하는 최솟값을 갱신하는 방법으로 해결하였습니다. 

 

 

<전체코드>

너무 조잡하여 참고할 것이 아니라 생각하지만... 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StringReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
	static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
	static StringBuilder output = new StringBuilder();
	static String src = "6\r\n"
			+ "0 1 2 3 4 5\r\n"
			+ "1 0 2 3 4 5\r\n"
			+ "1 2 0 3 4 5\r\n"
			+ "1 2 3 0 4 5\r\n"
			+ "1 2 3 4 0 5\r\n"
			+ "1 2 3 4 5 0";
	
	static int[][] data;
	static int Min,tempSUM1,tempSUM2;
	
	public static void main(String args[]) throws IOException {
		//input= new BufferedReader(new InputStreamReader(System.in));
		input = new BufferedReader(new StringReader(src));
		
		int N= Integer.parseInt(input.readLine());
		
		data= new int[N+1][N+1];
		Min=Integer.MAX_VALUE;
		
		StringTokenizer str;
		
		for(int i=1;i<N+1;i++) {
			str=new StringTokenizer(input.readLine());
			for(int j=1;j<N+1;j++) {
				data[i][j]=Integer.parseInt(str.nextToken());
			}
		}
		
		boolean[] visited=new boolean[N];
		int[] arr =new int[N];
		
		for(int i=0;i<N;i++) {
			arr[i]=i+1;
		}
		
		firstcombination(arr, visited, 0, N, N/2);
		
		System.out.println(Min);
		
	}
	
	
	// 백트래킹 사용
	static void firstcombination(int[] arr, boolean[] visited, int start, int n, int r) {
	    if(r == 0) {
	        
	        int[] subArr1=new int[n/2];
	        int[] subArr2=new int[n/2];
	        boolean[] subvisited=new boolean[n/2];
	        int j=0;
	        int k=0;
	        for(int i=0;i<n;i++) {
	        	if(visited[i]) {
	        		subArr1[j]=i+1;
	        		j++;
	        	}else {
	        		subArr2[k]=i+1;
		        	k++;	
	        	}
	        	
	        }
	        //System.out.println(Arrays.toString(subArr1)+" "+Arrays.toString(subArr2));
	        tempSUM1=0;
	        secondcombination(subArr1, subvisited, 0, n/2, 2);
	        tempSUM2=tempSUM1;
	        tempSUM1=0;
	        secondcombination(subArr2, subvisited, 0, n/2, 2);
	        //System.out.println(tempSUM1+" "+tempSUM2);
	        
	        Min=Math.min(Min, Math.abs(tempSUM1-tempSUM2));
	        return;
	    } 

	    for(int i=start; i<n; i++) {
	        visited[i] = true;
	        firstcombination(arr, visited, i + 1, n, r - 1);
	        visited[i] = false;
	    }
	}
	
	static void secondcombination(int[] arr, boolean[] visited, int start, int n, int r) {
	    if(r == 0) {
	     
	        
	        int temp[]=new int[2];
	        
	        int j=0;
	        for(int i=0;i<visited.length;i++) {
	        	if(visited[i]) {
	        		temp[j]=arr[i];
	        		j++;
	        	}
	        }
	        tempSUM1+=data[temp[0]][temp[1]];
	        tempSUM1+=data[temp[1]][temp[0]];
	        
	        return;
	    } 

	    for(int i=start; i<n; i++) {
	        visited[i] = true;
	        secondcombination(arr, visited, i + 1, n, r - 1);
	        visited[i] = false;
	    }
	}
	
}

 

너무 불필요한 계산이 많았다는 것을 채점 전에도 느꼈지만 부르트포스로 해결할 수 있는 문제답게 제한 조건이 널널하여 정답처리가 되었다.

다른 풀이들 중 실행 시간이 빠른 것들 중 꽂히는 풀이를 해석한 내용을 추가하고자 한다.

 

aa1aaaa11 님의 코드

 

Score( 0, N, 0, 0, 0, 0) 하면 전역변수로 선언한 answer에 구하고자 하는 답의 2배가 담기고 이를 2로 나누어 출력하고 끝난다

1번부터 1번 사람과 다른 사람들과의 시너지를 다 합한 후에 그 값을 

start 팀에 1번이 들어가는 경우로 가지치기하며 나머지 팀원까지 계산하면 

if문의 length == N에 걸려 answer 값을 갱신하고 끝

마찬가지로 link 팀에 들어가는 경우로... 계산 쭉.... 

여기까지는 대충 이해됬는데 왜 팀원이 될 사람과의 시너지만이 아니라 전체 사람들과의 시너지를 더하는지 

처음에 좀 이해하기 어려웠는데 왜 구분안하고 다 더해버리는지 처음 문제에 나와있는 예시로 따라가니 알 수 있었다.

 

1,2 가 팀 3,4 가 팀인 경우 계산되는 것을 수식으로 표현해보니 결국 필요없는 부분은 서로 중복되기에 두 값의 차를 구할 때 사라지고 필요한 부분은 중복되어 2를 나눠야 답이 나오는 것을 알 수 있었다.