Inor

[백준] 14889번 스타트와 링크 본문

Algorithm/백준

[백준] 14889번 스타트와 링크

Inor 2017. 12. 28. 13:09

- 문제 : https://www.acmicpc.net/problem/14889


 N명(짝수)의 사람들이 팀을 이루는 경우의 수를 모두 구하는 문제입니다. 모든 사람들은 특정 사람과 팀을 이루었을때 시너지 효과(능력치)가 높아지고 낮아집니다. 공평한 경기를 위해 팀을 구성 했을때, 2팀의 시너지 효과 차이가 가장 적은 경우를 찾는 문제입니다. 경우의 수를 구해서 해당 경우에 두 팀의 시너지 효과를 구하면 됩니다.




- 풀이


 모든 경우의 수를 탐색하기 위해서 깊이 탐색 알고리즘을 사용했습니다. 재귀를 이용해서 깊이 탐색을 했는데 N이 30이 넘어가면 연산이 안되는 경우가 발생했습니다. 이 부분은 추후에 스택으로 바꿔서 결과가 차이 나는지 확인해보겠습니다. 그리고 조합을 구현하기 위해서 중복을 피하는 방법을 사용했습니다. 각 사람에는 인덱스를 이용해서 중복을 줄였습니다.

 1,4,5 팀과 1,5,4 팀은 같은 시너지 효과를 내기 때문에 1,4,x 여기서 x의 사람을 채우기 위해서 무조건 3보다 큰 수부터 넣어주기로 했습니다. 1,4,2 -> 1,4,3 의 순서로 팀을 만드는 것이 아니라 1,4,5 -> 1,4,6 이렇게 x 자리의 사람을 찾을때 무조건 4보다 큰 인덱스의 사람부터 넣어줬습니다. 3,x,y 도 마찬가지로 x는 3보다 크게 y는 x보다 큰 인덱스로 채우며 팀이 만들어지는 경우의 수를 찾았습니다. setStartTeam(int count, int afterIndex) 메서드에서 afterIndex는 이전 사람의 인덱스 값을 나타내며, 새로 호출된 메서드에서 경우의 수를 찾는 시작 인덱스의 기준이 됩니다.

 setLinkTeam 메서드는 StartTeam이 만들어지고 남은 사람들을 이용해서 구성하도록 만들었습니다. 어떤 사람이 StartTeam이 됐는지 확인하기 위해 boolean[] hasTeam 변수를 선언해서 StartTeam에 포함된 사람들을 체크했습니다. false인 사람들은 아직 팀이 없는 사람이고 LinkTeam으로 배치 했습니다.




- 소스 코드


import java.util.Arrays;
import java.util.Scanner;

public class StartLink {
	Scanner sc;
	int N;
	int[][] scoreBoard;
	int[] startTeam, linkTeam;
	boolean[] hasTeam;
	int rNum, cNum;
	int result = 1000000;

	public void setValues() {
		sc = new Scanner(System.in);

		N = sc.nextInt();
		scoreBoard = new int[N + 1][N + 1];
		startTeam = new int[N / 2];
		linkTeam = new int[N / 2];
		hasTeam = new boolean[N + 1];

		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= N; j++) {
				scoreBoard[i][j] = sc.nextInt();
			}
		}
	}

	public void getScore() {
		int startScroe = 0;
		int linkScore = 0;
		int i, j;
		
		for (int row = 0; row < N / 2; row++) {
			for (int col = 0; col < N / 2; col++) {
				i = startTeam[row];
				j = startTeam[col];
				startScroe += scoreBoard[i][j];
				
				i = linkTeam[row];
				j = linkTeam[col];
				linkScore += scoreBoard[i][j];
			}
		}
		
		int tempResult = Math.abs(startScroe - linkScore);
		if (result >= tempResult) {
			result = tempResult;
		}
	}
	
	public void setLinkTeam(){
		int linkTeamIndex = 0;
		for(int i=1;i<=N;i++){
			if(hasTeam[i] == false){
				linkTeam[linkTeamIndex++] = i;
			}
		}
	}
	
	public void resetLinkTeam(){
		Arrays.fill(linkTeam, 0);
	}

	public void setStartTeam(int count, int afterIndex) {
		if (count >= N / 2) {
			setLinkTeam();
			getScore();
			resetLinkTeam();
			return;
		}

		for (int pIndex = afterIndex + 1; pIndex <= N; pIndex++) {
			startTeam[count] = pIndex;
			hasTeam[pIndex] = true;
			count++;
			
			setStartTeam(count, pIndex);
			
			hasTeam[pIndex] = false;
			count--;
		}

	}

	public void solve() {
		setValues();
		int count = 0;

		for (int pIndex = 1; pIndex <= N; pIndex++) {
			startTeam[count] = pIndex;
			hasTeam[pIndex] = true;
			count++;
			
			setStartTeam(count, pIndex);
			
			hasTeam[pIndex] = false;
			count--;
		}
		System.out.println(result);
	}

	public static void main(String[] args) {
		StartLink m = new StartLink();
		m.solve();
	}

}


'Algorithm > 백준' 카테고리의 다른 글

[백준] 1932번 숫자 삼각형  (0) 2018.01.10
[백준] 14890번 경사로  (0) 2018.01.03
[백준] 9324번 진짜 메시지  (0) 2017.12.20
[백준] 2851번 슈퍼 마리오  (0) 2017.12.18
[백준] 10250번 ACM 호텔  (0) 2017.12.10
Comments