[백준] 14889. 스타트와 링크 (Java)

문제

https://www.acmicpc.net/problem/14889

14889번: 스타트와 링크

 

풀이 1

0. 문제 해석

두 팀으로 나눠야 하므로 인원이 4명일 경우

4C2 , 나머지 2명 로 나뉠 것이고

6명이면

6C3, 나머지 3명 으로 나뉠것이다.

이제 나뉜 팀들의 능력치의 합의 차이가 최소가 되는 값을 찾는다.

 

즉, 위와 같은 알고리즘을 코드로 구현하면 되는데, 조합의 수가 계속 늘어날수록

반복해야 하기 때문에 재귀 방식으로 조합을 사용한다.

 

1. 능력치 입력

2. 조합 생성

재귀방식으로 조합을 구현하여 선택된 번호들을 list에 저장한다.

그 후 조합이 종료되었을 때 그 조합은 start팀의 선수 번호, 그 리스트에 포함되지 않은 값들은 link 팀에게 배정한다.

 

주석처리 해놓은 부분으로 확인해보면 팀 배정을 쉽게 확인할 수 있다.

 

 

3. 조합 능력치 차이 최솟값 찾기

이제 팀에 대한 선수번호의 능력치 값들을 다 더해준 후,

차이를 절댓값을 통하여 구한다.

 

4. 전체 코드

// [백준] 14889. 스타트와 링크 (Java)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
	static int n;
	static int min = 101;
	static int[][] arr;
	static StringTokenizer st;

    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    	n = Integer.parseInt(br.readLine());
    	arr = new int[n + 1][n + 1];

    	// 능력치 입력
    	for(int i = 1; i <= n; i++) {
    		st = new StringTokenizer(br.readLine());
    		for(int j = 1; j <= n; j++) {
    			arr[i][j] = Integer.parseInt(st.nextToken());
    		}
    	}

    	combi(new ArrayList<Integer>(), 1, n / 2);

    	System.out.println(min);
    }

    // 조합 생성
    public static void combi(ArrayList<Integer> start, int index, int count) {
    	if(count == 0) {
    		ArrayList<Integer> link = new ArrayList<>();
    		// 남은 사람들의 조합 (link 팀)
    		for(int i = 1; i <= n; i++) {
    			if(!start.contains(i)) {
    				link.add(i);
    			}
    		}
//    		System.out.print("[start] " + start + " ");
//    		System.out.println("[link] " + link);

    		solve(start,link);
    		return;
    	}

    	// start 팀 조합 생성
    	for(int i = index; i <= n; i++) {
    		start.add(i);
    		combi(start, i + 1, count - 1);
    		start.remove(start.size() - 1);
    	}
    }

    // 조합별 능력치 차이 최솟값 찾기
    public static void solve(ArrayList<Integer> start, ArrayList<Integer> link) {
    	int startSum = 0;
    	int linkSum = 0;

    	for(int i = 0; i < start.size() - 1; i++) {
    		for(int j = i + 1; j < start.size(); j++) {
    			int x = start.get(i);
    			int y = start.get(j);
    			startSum += arr[x][y] + arr[y][x];
    		}
    	}

    	for(int i = 0; i < link.size() - 1; i++) {
    		for(int j = i + 1; j < link.size(); j++) {
    			int x = link.get(i);
    			int y = link.get(j);
    			linkSum += arr[x][y] + arr[y][x];
    		}
    	}

    	int result = Math.abs(startSum - linkSum);
    	min = Math.min(min, result);
//    	System.out.println(startSum - linkSum);
    }
}

하지만 위 방법은 전체를 탐색하기 때문에 시간과 메모리 면에서 효율적이지 못하다.

따라서 최솟값이 0이라면 즉시 종료 처리해주고, 조합을 만들때에도 새로운 list를 생성하는 것이 아닌 방문처리를 이용하여 효율적으로 구현할 수 있다.

 

풀이 2

1. 방문 배열로 조합 생성

숫자를 뽑을 때 리스트에 추가하는 것이 아닌

그 수를 방문했다고 처리한다. 그러면 조합 생성이 종료 되었을 때 true인 n/2 명의 선수는 같은 팀이고, false인 n/2 명의 선수는 같은 팀일 것이다.

 

2. 최솟값 찾기

이제 전체를 순회하면서

visit 여부에 따라 팀을 배정해주고,

min이 0이면 즉시 리턴하도록 한다.

 

3. 전체 코드

// [백준] 14889. 스타트와 링크 (Java)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	static int n;
	static int min = 101;
	static int[][] arr;
	static boolean[] visit;
	static StringTokenizer st;
	
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	
    	n = Integer.parseInt(br.readLine());
    	arr = new int[n + 1][n + 1];
    	visit = new boolean[n + 1];
    	
    	// 능력치 입력
    	for(int i = 1; i <= n; i++) {
    		st = new StringTokenizer(br.readLine());
    		for(int j = 1; j <= n; j++) {
    			arr[i][j] = Integer.parseInt(st.nextToken());
    		}
    	}
    	
    	combi(1, n / 2);
    	
    	System.out.println(min);
    }
    
    // 조합 생성
    public static void combi(int index, int count) {
    	if(count == 0) {
    		solve();
    		return;
    	}
    	
    	// start 팀 조합 생성
    	for(int i = index; i <= n; i++) {
    		visit[i] = true; 
    		combi(i + 1, count - 1);
    		visit[i] = false;
    	}
    }
    
    // 조합별 능력치 차이 최솟값 찾기
    public static void solve() {
    	int startSum = 0;
    	int linkSum = 0;
    	
    	for(int i = 1; i <= n - 1; i++) {
    		for(int j = i + 1; j <= n; j++) {
    			if(visit[i] == true && visit[j] == true) {
    				startSum += arr[i][j] + arr[j][i];
    			}
    			else if(visit[i] == false && visit[j] == false) {
    				linkSum += arr[i][j] + arr[j][i];
    			}
    		}
    	}
    	
    	int result = Math.abs(startSum - linkSum);
    	min = Math.min(min, result);
    	
    	// 0보다 작을 순 없으므로 즉시 종료
    	if(min == 0) {
    		System.out.println(min);
    		System.exit(0);
    	}
    }
}

 

좀 더 효율적인 결과를 얻을 수 있다.