[BOJ] 14889번 스타트와 링크 - JAVA

💡 문제

💬 입출력 예시

📌 풀이(소스코드)

import java.util.Scanner;

public class Main {
	private static int n;
	private static int[][] S;
	private static boolean[] visited;
	private static int min = Integer.MAX_VALUE;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		// 입력
		n = sc.nextInt();
		S = new int[n][n];
		visited = new boolean[n];
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				S[i][j] = sc.nextInt();
			}
		}
		combination(0, 0);
		System.out.println(min);
	}

    private static void combination(int cnt, int start) {
        if (cnt == n/2) {
        	getMin();
            return;
        }
        for (int i = start; i < n; i++) {
        	if (!visited[i]) {
        		visited[i] = true;
        		combination(cnt + 1, i + 1);
        		visited[i] = false;
        	}
        }
    }
    
    private static void getMin() {
    	int startTeam = 0;
    	int linkTeam = 0;
    	int diff = 0;
    	
		for (int i = 0; i < n - 1; i++) {
			for (int j = i + 1; j < n; j++) {
				// i 번째 사람과 j 번째 사람이 true라면 스타트팀으로 점수 플러스
				if (visited[i] && visited[j]) {
					startTeam += S[i][j];
					startTeam += S[j][i];
				}
				// i 번째 사람과 j 번째 사람이 false라면 링크팀으로 점수 플러스
				else if (!visited[i] && !visited[j]) {
					linkTeam += S[i][j];
					linkTeam += S[j][i];
				}
			}
		}
    	diff = Math.abs(startTeam-linkTeam);
    	
    	// 최솟값 계산
    	min = Math.min(min, diff);
    }
}

📄 해설

• 조합을 사용하여 해결하는 문제
• 조합을 사용하여 각 조합마다 차이를 계산하고, 최솟값을 갱신
• 작성자의 설명보다, 코드와 주석을 함께보고 이해하는 것이 더 나을것이다