[삼성SW테스트] 백준 14889 스타트와 링크

 

 

 

백준 조합 문제

#14889 - 스타트와 링크

 

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

 

 

사용한 개념

 

기본적으로 조합을 구하는 문제입니다. 순열과 조합에 대해서 기본적으로 구별하고 구할 수 있어야합니다. 순열과 조합에 대해서 잘 모르겠으면...아래 링크를 참고하세요..

 

2019/03/23 - [프로그래밍/Java] - [JAVA] 조합,중복조합,순열,중복순열 소스

 

제가 생각한 프로세스는 다음과 같습니다.

 

1. 일단 스타트팀만 구한다. (조합)

2. 스타트 팀 팀원을 구하면, 자동으로 링크 팀을 구할 수 있음.

3. 각 팀 안에서 2명씩 짝지어, 능력치를 구한다. 

4. 3번에서 구해진 각 팀의 능력치의 차이가 제일 작으면 계속 갱신...

5. 1-4 번 모든 경우에 수를 다 구한다. (결국 1번에서 모든 조합의 경우의 수를 구하는 것과 동일)

 

 

아래는 전체소스입니다. 궁굼하신 점은 댓글 남겨주세요~

 

 

 

전체소스

package RESAMSUNG;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class BackJoon_14889 {

	static int[][] stats;
	static int ans = Integer.MAX_VALUE;
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader rc = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(rc.readLine());
		
		stats = new int[n][n];
		
		for(int i=0; i<stats.length; i++){
			String str = rc.readLine();
			String[] strArr = str.split(" ");
			for(int j=0; j<stats[0].length; j++){
				stats[i][j] = Integer.parseInt(strArr[j]);
			}
		}
		
		//n팀에서 n/2 조합..
		int[] startTeam = new int[n/2];
		getTeam(startTeam, n, n/2, 0, 0);
		
		System.out.println(ans);

	}

	private static void getTeam(int [] startTeam, int n, int r, int index, int target) {
		if(r == 0){
			int linkTeam[] = new int[n/2];
			int idx = 0;
			for(int i=0; i<n; i++){
				boolean flag = true;
				for(int j=0; j<startTeam.length; j++){
					if(i == startTeam[j]) flag = false;
				}
				if(flag) linkTeam[idx++] = i;
			}
			
			//능력치 구하기
			//팀안에서도 2명씩 짝지어서 능력치 합 구하기
			int gap = Math.abs(getTeamStats(startTeam) - getTeamStats(linkTeam));
			if(ans > gap) ans = gap;
			
			return;
		}else if(target == n)return;
		
		startTeam[index] = target;
		getTeam(startTeam, n, r-1, index+1, target+1);
		getTeam(startTeam, n, r, index, target+1);
		
	}

	private static int getTeamStats(int[] team) {
		
		int sum = 0;
		for(int i=0; i<team.length-1; i++){
			for(int j=i+1; j<team.length; j++){
				sum += stats[team[i]][team[j]];
				sum += stats[team[j]][team[i]];
			}
			
		}
		return sum;
		
	}

}