[백준] 14889번 : 스타트와 링크 (JAVA)

저번에 삼성 SW 역량 테스트 기출문제 1번인 "연산자 끼워넣기" 문제에 이어서

이번에는 기출문제 2번인 "스타트와 링크" 문제를 풀었다.

 

백트래킹에 대해 아직 이해하지 못했다면 다음의 블로그에서 확인하면 된다.

https://lucy1215.tistory.com/3

알고리즘 - 백트래킹(Backtracking)

 

바로 앞 문제인 14888번 : 연산자 끼워넣기에 대한 내용은 다음의 블로그에서 확인하면 된다.

https://lucy1215.tistory.com/13

[백준] 14888번 : 연산자 끼워넣기 (JAVA)

---

<문제>

 

<문제 해석>

백트래킹을 이용하여 사람의 수와 각 사람과 사람간의 능력치가 주어졌을 때, N/2명으로 이루어진 스타트팀과 링크팀의

각각의 능력치 합의 차이가 최소가 되는 값을 구해라.

 

 

<문제 해결>

앞에서 풀었던 "연산자 끼워넣기" 문제와 같은 유형의 백트래킹 문제이다.

 

문제에서 나온 예제로 한번 더 설명을 하자면,

팀을 이루는 경우는

• 1번-2번  / 3번-4번
• 1번-3번  / 2번-4번
• 1번-4번  / 2번-3번

총 3가지가 있다.

 

첫번째부터 하나씩 보면,

 

1️⃣(스타트팀) 1번과 2번 / (링크팀) 3번과 4번이 팀을 이뤘을 때,

스타트팀의 능력치 : 1 + 4 = 5

링크팀의 능력치 : 2 + 5 = 7

👉능력치의 차 : 7 - 5 = 2

 

 

 

2️⃣(스타트팀) 1번과 3번 / (링크팀) 2번과 4번이 팀을 이뤘을 때,

스타트팀의 능력치 : 2 + 7 = 9

링크팀의 능력치 : 6 + 4 = 10

👉능력치의 차 : 10 - 9 = 1

 

 

 

3️⃣(스타트팀) 1번과 4번 / (링크팀) 2번과 3번이 팀을 이뤘을 때,

스타트팀의 능력치 : 3 + 3 = 6

링크팀의 능력치 : 5 + 1 = 6

👉능력치의 차 : 6 - 6 = 0

 

 

<결론>

1번째 : 2

2번째 : 1

3번째 : 0

로 최종 최솟값은 0이 된다.

 

💡모든 경우의 수, 즉 조합에 대한 경우의 수를  탐색하여 최솟값 비교하여 찾아낸다.

 

 

<알고리즘>

1. 능력치의 값을 2차원 배열인 ar에 담는다.

2. 조합에 대한 함수 combination() 생성

• 방문 여부에 대한 배열 visit
• index = n/2 값이라면 cal() 함수 호출
• index != n/2 값이라면 재귀호출

3. 능력치 계산하는 함수 cal() 생성

• visit의 값이 true인 수끼리 팀 / false인 수끼리 팀
• 팀 별 능력치 계산 후 최솟값 비교

 

 

<코드>

import java.io.IOException;
import java.util.Scanner;

public class Main {	
	static int n;
	static int[][] ar;
	static boolean[] visit;
	static int result = Integer.MAX_VALUE;
	
	public static void main(String[] args) throws IOException {
		
		Scanner sc = new Scanner(System.in);
		
		n = sc.nextInt();
		ar = new int[n][n];
		visit = new boolean[n];
		
		for(int i=0;i<n;i++) {
			for(int j=0;j<n;j++) {
				ar[i][j] = sc.nextInt();
			}
		}
		
		combination(0, 0);
		System.out.println(result);
	}
	
	//N/2의 경우의 수
	static void combination(int location, int index) {
		
		if(index == n/2) {
			cal();
			return;
		}
		
		for(int i=location;i<n;i++) {
			if(!visit[i]) {
				visit[i] = true;
				combination(i+1, index+1);
				visit[i] = false;
			}
		}
	}
	
	//능력치 계산
	static void cal() {
		
		int start =0;
		int link = 0;
		
		for(int i=0;i<n-1;i++) {
			for(int j=i+1;j<n;j++) {
				if(visit[i] == true && visit[j] == true) {
					start += ar[i][j];
					start += ar[j][i];
				}
				
				else if(visit[i] == false && visit[j] == false) {
					link += ar[i][j];
					link += ar[j][i];
				}
			}
		}
		
		int total = Math.abs(start - link);
		result = Math.min(total, result);
	}
}

 

 

---

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

14889번: 스타트와 링크