14889번) 스타트와 링크

문제 출처 : https://www.acmicpc.net/problem/14889

2018년 4월 6일 - 다듬지 않은 시험 코드 (30분) public class Q14889 { static boolean[] isVisit; static int people, halfPeople, minResult = -1; static int[][] values; public static void main(String[] args) { Scanner sc = new Scanner(System.in); people = sc.nextInt(); halfPeople = people / 2; isVisit = new boolean[people]; values = new int[people][people]; for (int i = 0; i < people; i++) { for (int j = 0; j < people; j++) { values[i][j] = sc.nextInt(); } } for (int i = 0; i < people; i++) { isVisit[i] = true; selectPeople(i, 1, 0); isVisit[i] = false; } System.out.println(minResult); } static void selectPeople(int num, int count, int startTeamPower) { if (count > 1) { for (int i = 0; i < people; i++) { if (i != num && isVisit[i]) { startTeamPower += values[i][num]; startTeamPower += values[num][i]; } } } if (halfPeople == count) { int linkTeamResult = 0; for (int i = 0; i < people; i++) { if (!isVisit[i]) { for (int j = 0; j < people; j++) { if (i != j && !isVisit[j]) { linkTeamResult += values[i][j]; } } } } // System.out.println(linkTeamResult + " / " + startTeamPower); int result = linkTeamResult - startTeamPower; if (result < 0) { result*= -1; } if (minResult == -1 || minResult > result) { minResult = result; } return ; } for (int i = num+1; i < people; i++) { isVisit[i] = true; selectPeople(i, count+1, startTeamPower); isVisit[i] = false; } } }

2018년 4월 12일 - 다듬지 않은 코드 (소요시간 13분) import java.util.Scanner; public class Q14889 { static int size, result = -1; static int[][] map; static boolean[] isVisit; public static void main(String[] args) { Scanner sc = new Scanner(System.in); size = sc.nextInt(); map = new int[size][size]; isVisit = new boolean[size]; for (int i = 0; i < size; i++) { for (int j = 0 ; j < size; j++) { map[i][j] = sc.nextInt(); } } for (int i = 0; i < size; i++) { isVisit[i] = true; selectPeople(i, 1); isVisit[i] = false; } System.out.println(result); } static void selectPeople(int num, int count) { if (count >= size/2) { int firstTeamResult = 0, secondTeamResult = 0; for (int i = 0; i < size; i++) { for (int j = 0 ; j < size; j++) { if (isVisit[i] && isVisit[j]) { firstTeamResult += map[i][j]; } else if (!isVisit[i] && !isVisit[j]) { secondTeamResult += map[i][j]; } } } int tempResult = firstTeamResult - secondTeamResult; if (tempResult < 0) { tempResult *= -1; } if (result == -1 || result > tempResult) { result = tempResult; } return; } for (int i = num+1; i < size; i++) { isVisit[i] = true; selectPeople(i, count+1); isVisit[i] = false; } } }