💔 14889. 스타트와 링크

목차
1. 문제 설명
2. 푼 원리 설명 
3. 코드

 

1. 문제 설명 

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

14889번: 스타트와 링크

2. 푼 원리 설명 

일단 나는 이거 답지 봤다.

(1) 팀을 조합으로 반으로 나눈다. -> (2) 각 팀 멤버간의 시너지 계산 -> (3) 차 구해서 그 차가 지금까지의 값 중 최소일 경우 갱신 

요거까지는 생각을 했는데,  (2)도 조합으로 스타트팀 내에서 2명씩 짝을 잡아서 값을 계산 해야 한다고 생각했다. 그러면 경우의 수가 기하급수적으로 늘어난다. 

하지만 답을 보니, 시너지는 2명씩 짝을 지어서 그 둘 사이의 시너지만 다 더하는 것이 아니었고, 
(나의 생각: A,B,C,D가 스타트 팀이면 A,B / C,D 로 짝 지어서 각 시너지 계산하고 그 시너지의 총합이 스타트팀의 총합 )

근데 이게 아니라 그냥 같은팀 멤버끼리 일어나는 모든 시너지의 총합이 답이었다.
(A,B,C,D가 스타트 팀이면 , A 와 B,C,D의 시너지, B 와 C,D의 시너지, C와 D의 시너지의 총합 )

-> 이걸 조합으로 구해야 한다고 생각했는데, 그냥 2차원 배열 돌면서 모든 시너지를 더하면 되었다. 

 

3. 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.sql.Array;
import java.util.*;

// 14889번 스타트와 링크
public class Main {

    // 사용할 기술: 조합
    // 푸는 방법
        // (A) 반으로 팀 나누기 -> 방문 배열로 갈라진 A팀, B팀 멤버 명시
        // (B) A팀 총 시너지, B팀 총 시너지 계산 -> 각 팀별로 조합
        // (C) 능력치 차이가 최소인지 확인, 현재까지 최소면 능력치 차이 변수 갱신



    // * 입력 받기 위한 변수
    static int N;
    static int [][] arr;

    // * 반 나누기 위한 방문 배열
    static boolean [] isVisited;

    // * 나눠진 팀용 -> 선수 담기/ 선수들의 방문 배열



    // * 최소 시너지 차
    static int subtraction = Integer.MAX_VALUE;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));


        // 1) 입력 받기
        N = Integer.parseInt(br.readLine());
        arr = new int[N+1][N+1];
        isVisited = new boolean[N+1];

        for (int i = 1; i <= N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= N; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        selectHalf(1,1);

        System.out.println(subtraction);
    }

    // 2) 반으로 나누기
    public static void selectHalf(int cnt, int start) {

        if(cnt > N/2){

            calculate();

            return;
        }

        for (int i = start; i <= N; i++) {
            if(!isVisited[start]){
                isVisited[start] = true;
                selectHalf(cnt+1, i+1);
                isVisited[start] = false;
            }
        }
    }


    // true 팀에서 2명을 뽑아서 시너지를 계산한 후 tureTeamAmount에 집어넣는다.
    // false 팀에서 2명을 뽑아서 시너지를 계산한 후 falseTeamAmount에 집어넣는다.

    public static void calculate() {

        int trueTeam = 0;
        int falseTeam = 0;

        for (int i = 1; i <= N -1 ; i++) {
            for (int j = i+1; j <= N; j++) {
                if( isVisited[i] && isVisited[j]){
                    trueTeam += arr[i][j] + arr[j][i];
                }

                if(!isVisited[i] && !isVisited[j]){
                    falseTeam += arr[i][j] + arr[j][i];
                }
            }
        }

        subtraction = Math.min(subtraction, Math.abs(trueTeam - falseTeam));
    }
    
}