[백준] 14889. 스타트와 링크(실버3)
백준(실버3) - 14889. 스타트와 링크(실버3)
풀이
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static int[][] map;
static int n;
static int MIN = Integer.MAX_VALUE;
static boolean[] isSelected;
static int[] linkTeam;
static int[] startTeam;
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(br.readLine());
isSelected = new boolean[n];
startTeam = new int[n/2];
linkTeam = new int[n/2];
map = new int[n][n];
for(int i = 0; i<n; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
for(int j=0; j<n; j++) {
map[i][j] = Integer.parseInt(st.nextToken());
}
}
combination(0, 0);
System.out.println(MIN);
}
static int diff() {
int sum1=0;
int sum2 = 0;
for(int i=0; i<startTeam.length-1; i++) {
for(int j=i+1; j<startTeam.length; j++) {
int x = startTeam[i];
int y = startTeam[j];
sum1 += map[x][y] + map[y][x];
}
}
for(int i=0; i<linkTeam.length-1; i++) {
for(int j=i+1; j<linkTeam.length; j++) {
int x = linkTeam[i];
int y = linkTeam[j];
sum2 += map[x][y] + map[y][x];
}
}
int min = Math.abs(sum1-sum2);
return min;
}
static void combination(int cnt, int start) {
if(cnt == n/2) {
int idx = 0;
for(int i=0; i<n; i++) {
if(isSelected[i] == false) {
linkTeam[idx++] = i;
}
}
int result = diff();
MIN = Math.min(MIN, result);
return;
}
for(int i=start; i<n; i++) {
isSelected[i] = true;
startTeam[cnt] = i;
combination(cnt+1, i+1);
isSelected[i] = false;
}
}
}
Author And Source
이 문제에 관하여([백준] 14889. 스타트와 링크(실버3)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@humblechoi/백준저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)