[14889] 스타트와 링크

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

---

이것도 SW 역량테스트 문제중에 쉬운편에 속하는 브루트 포스문제라고 생각합니다..... 이번에는 정답을 안보고 풀긴 했는데, 너무 조잡하게 푼 것 같습니다...ㅋ 이 문제도 입력 N이 20이하이기 때문에 N/2 명의 사람들이 팀을 이룰 수 있는 모든 경우를 출력해서 스타트팀과 링크팀의 능력치를 빼서 절댓값으로 최솟값을 구했습니다.

[6603] 로또 https://daily-life-of-bsh.tistory.com/58 문제의 코드를 참고하면 어렵지 않게 풀 수 있는 문제였습니다.

< 문제 풀이 >

1. 저는 팀의 member 의 번호를 list 라는 배열에 저장 했습니다. 처음에 보면 list[0] ~ list[N-1] 까지 숫자 1부터 N 까지 넣는데, N명의 사람의 번호를 list 에 저장한 것입니다.

2. 그리고 recur(0, 0)을 호출해서 백트래킹을 하는데, team 이라는 배열에 스타트팀의 멤버를 저장했습니다. 그래서 스타트팀의 멤버가 people 명 뽑으면 이제 능력치 계산을 하게 됩니다. people은 N/2 로 한 팀원의 수를 뜻합니다.

3. 그래서 스타트팀의 멤버 people명이 뽑히면, 링크 팀의 멤버를 저장할 ArrayList link_mem에 스타트팀의 멤버를 제외한 나머지 팀원의 번호를 저장합니다. 스타트팀의 사람들을 제외한 사람을 뽑을 때 mark 라는 boolean 변수를 두어서 list 에 있는 숫자가 스타트팀의 있는 사람이면 true 로 바꿔주어 표시해주었습니다. 이제 mark배열에 false 를 체크하면 링크팀의 멤버가 구해 집니다. 그래서 그 멤버들을 link_mem 에 넣고  각 팀의 능력치값을 계산합니다.

4. 마지막으로 모든 뽑힐 수 있는 팀원의 능력치를 빼고 절댓값을 비교해주면서 최솟값을 result 에 저장하고 출력합니다.

---

import java.util.Scanner;
import java.util.ArrayList;

// 14889 스타트와 링크
public class Main {
	static int N, people, start_score, link_score, result = 987987987;
	static int [][] arr;
	static int [] list, team;
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		people = N/2;
		arr = new int[N][N];
		list = new int[N];
		team = new int[N];
		
		int num = 1;
		
		// 스타트링크 다니는 사람들의 수를 list 배열에 저장
		for(int i=1; i<=N; i++) {
			list[i-1] = num++; 
		}
		
		// 능력치 조사
		for(int i=0; i<N; i++) {
			for(int j=0; j<N; j++) {
				arr[i][j] = sc.nextInt();
			}
		}
		
		// 백트래킹
		recur(0, 0);
		System.out.println(result);
	}
	
	public static void recur(int start, int depth) {
		
		// 한팀의 인원 수 만큼 뽑았을 때
		if(depth == people) {
			
			// link 팀의 member 번호를 저장하는 ArrayList
			ArrayList<Integer> link_mem = new ArrayList<Integer>();
			
			// start 팀의 member 를 제외한 link 팀 멤버를 뽑기 위해 표시할 mark 변수
			boolean [] mark = new boolean[N];
			for(int i=0; i<people; i++) {
				for(int j=0; j<N; j++) {
					if(team[i] == list[j]) mark[j] = true;
				}
			}
			for(int i=0; i<N; i++) {
				if(mark[i] == false) {
					link_mem.add(list[i]);					
				}
			}
						
			start_score = 0;
			link_score = 0;
			
			// start 팀과 link 팀의 점수 계산
			for(int i=0; i<people; i++) {
				for(int j=i; j<people; j++) {
					start_score += arr[team[i]-1][team[j]-1];
					start_score += arr[team[j]-1][team[i]-1];
					link_score += arr[link_mem.get(i)-1][link_mem.get(j)-1];
					link_score += arr[link_mem.get(j)-1][link_mem.get(i)-1];
				}
			}
			int min = Math.abs(start_score-link_score);
			result = Math.min(result, min);
			return;
		}
		
		for(int i=start; i<N; i++) {
			team[depth] = list[i];
			recur(i+1, depth+1);
		}
	}
}