백준 14889번 : 스타트와 링크

 문제

www.acmicpc.net/problem/14889

14889번: 스타트와 링크

14889 스타트와 링크

 

 구현 방법

 저는 조합을 두 번 사용해서 풀어주었습니다. 방법을 단계로 나누어 생각해보았습니다.

1. 조합 개수 구하기

일단 조합의 개수를 구해줬습니다. 조합들을 구해보니 만약 N이 4일 때 (1, 2) (1, 3) (1, 4) (2, 3) (2, 4) (3, 4) 로 6개 입니다. 

이 조합으로 능력치를 다 계산해봐도 좋지만 스타트 팀이 (1, 2)일 때 링크 팀은 (3, 4), 스타트 팀이 (3, 4)일 때 링크 팀은 (1, 2) 의 결과값은 같으므로 중복을 피해주기 위해 방법을 생각해보았습니다.

스타트 팀이 (1, 2)이면 링크 팀이 (3, 4) 

스타트 팀이 (1, 3)이면 링크 팀이 (2, 4)

스타트 팀이 (1, 4)이면 링크 팀이 (2, 3) 입니다.

이렇게 보면 조합의 반절만 구하여 구한쪽이 스타트 팀 나머지가 링크 팀으로 구분하여 계산하면 훨씬 시간을 줄일 수 있다는 걸 알 수 있습니다. 

 

2. 팀원을 N/2명씩 뽑는 조합

조합의 개수가 조합 전체의 개수/2 이면 조합 구하는 걸 멈추게 해주었습니다.

현재 조합 배열은 스타트 팀으로 선택되지 않은 팀원들이 있는 링크 팀을 구해주었습니다.

 

3. 각 팀원 2명씩의 능력치 구하기

조합을 한 번 더 사용해서 각 팀원 중 2명씩 뽑아 능력치를 각 팀 능력치에 더해주었습니다.

 

4. 능력치 최솟값 구하기

Math.min 함수를 사용하여 현재까지에서의 최솟값과 현재의 최솟값을 비교해 더 작은 값을 최솟값으로 설정하여 출력하면 끝!!

 

 구현 코드

package BOJ.Silver;

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

public class B14889_스타트와링크 {
	static int N, stop, sumS, sumL, MIN;
	static long cnt;
	static int[][] ability;
	static int[] startT, numbers2, linkT;
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		ability = new int[N+1][N+1];
		startT = new int[N/2];
		linkT = new int[N/2];
		numbers2 = new int[2];
		for (int i=1;i<=N;i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			for (int j=1;j<=N;j++) {
				ability[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		// 조합 개수 구하기
		long p = 1;
		for (int i=N;i>N/2;i--) {
			p*=i;
		}
		long q = 1;
		for (int i=N/2;i>0;i--) {
			q*=i;
		}
		cnt=(p/q)/2;
		
		MIN = Integer.MAX_VALUE;
		combination(0, 1); // 팀 나누기
		System.out.println(MIN);
	}
	
	static void combination(int num, int start) {
		if (num==N/2) {
			stop++;
			linkT();
			return;
		}
		
		for (int i=start;i<=N;i++) {
			startT[num] = i;
			combination(num+1, i+1);
			if (stop==cnt) return; // 팀 나누기 조합 개수가 전체 조합 수의 반절이면 그만
		}
	}
	
	static void linkT() {
		sumS = 0; sumL = 0;
		int sizeS = 0, sizeL = 0;
		for (int i=1;i<=N;i++) {
			if (sizeS<N/2 && startT[sizeS]==i) sizeS++;
			else linkT[sizeL++] = i;
		}
		combination2(0, 0, startT, 'S'); // 2명씩 능력치 구하기
		combination2(0, 0, linkT, 'L'); // 2명씩 능력치 구하기
		MIN = Math.min(MIN, Math.abs(sumL-sumS));
	}
	
	static void combination2(int num, int start, int[] team, char T) {
		if (num==2) {
			diff(T);
			return;
		}
		
		for (int i=start;i<N/2;i++) {
			numbers2[num] = team[i];
			combination2(num+1, i+1, team, T);
		}
	}
	
	static void diff(char T) {
		if (T=='S') {
			sumS+=ability[numbers2[0]][numbers2[1]];
			sumS+=ability[numbers2[1]][numbers2[0]];
		} else if (T=='L') {
			sumL+=ability[numbers2[0]][numbers2[1]];
			sumL+=ability[numbers2[1]][numbers2[0]];
		}
	}
}

 

정답!