백준 14889번: 스타트와 링크 :: 매운코딩
728x90
300x250

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

 

14889번: 스타트와 링크

예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다.

www.acmicpc.net

백준14889번 스타트와 링크

 

 

 

1.  먼저 N/2개만큼 뽑기 ( 순서상관 없는 조합)

2. 뽑은 것들의 순서를 따져서 능력치 계산 (스타트팀)

3. 안뽑은 것들도 능력치 계산 (링크팀)

4. 둘의 차이 비교 후 가장 낮은 대소를 가지는 것이 몇인지 출력.

 

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.*;

public class Main {

	public static int N, start=0,link=0;
	public static int[][] map;
	public static int[] arr;
	public static boolean[] visit;
	public static int min = Integer.MAX_VALUE;
	public static void main(String[] args)  {
		
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		map = new int[N+1][N+1];
		arr = new int[N/2];
		visit = new boolean[N+1];
		
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= N; j++) {
				map[i][j] = sc.nextInt();
			}
		}
		
		
		dfs(1,0);
		System.out.println(min);
	}
	
	public static void dfs(int num, int idx) {
		//종료조건
		//한 팀이꾸려졌는지?
		if(idx==N/2) {
			start=0;
			link=0;
			//링크팀 경우의 수 계산
			int[] arr2 = new int[N/2];
			int n=0; //idx역할
			for (int i = 1; i < visit.length; i++) {
				if(!visit[i])
					arr2[n++]=i;
			}
			
			//스타트팀 능력치 계산
			//perm(arr,0);
			for (int i = 0; i < arr.length; i++) {
				for (int j = 0; j < arr.length; j++) {
					if(arr[i]!=arr[j])
						start+=map[arr[i]][arr[j]];
				}
			}
			//링크팀 능력치 계산
			//perm(arr2,0);
			for (int i = 0; i < arr2.length; i++) {
				for (int j = 0; j < arr2.length; j++) {
					if(arr2[i]!=arr2[j])
						link+=map[arr2[i]][arr2[j]];
				}
			}
			//대소비교
			min = Math.min(min, Math.abs(start-link));
			return;
		}
		
		//N/2개만큼 뽑기
		for (int i = num; i <= N; i++) {
			if(visit[i])
				continue;
			
			visit[i]=true;
			arr[idx]=i;
			dfs(i,idx+1);
			visit[i]=false;

		}
	}

}
728x90

'알고리즘 > 조합 & 순열' 카테고리의 다른 글

SWEA - 8338. 계산기  (0) 2020.05.15
SWEA - 5215. 햄버거 다이어트  (0) 2020.05.15
백준 14888번: 연산자 끼워넣기  (0) 2020.03.10
백준 15655번: N과 M (6)  (0) 2020.03.04
백준 15654번: N과 M (5)  (0) 2020.03.04

+ Recent posts