Baekjoon(白駿)14889号

💻 Beakjoon 14889題-Java

Baekjoon 14889号

問題の説明

今日はスタート地点を走る人が集まってサッカーをします.サッカーは平日の午後に行われ、義務参加でもない.サッカーをするために集まったのは全部でN人で、不思議なことにNは偶数です.今はN/2人からなるスタートチームとリンクチームに分けます.
BOJを運営する会社のように、1からNの番号を割り当て、以下の能力値を調べた.コンピテンシー値Sijは、i番とj番が同じチームに属する場合、チームに追加されるコンピテンシー値です.チームのコンピテンシー値は、チーム内のすべてのコンピテンシー値Sijの和です.SijはSjiとは異なり、i番とj番が同じチームに属している場合、チームで増加した能力値はSijとSjiです.
N=4,Sは以下のようになります.
j\i123410123240563710243450
たとえば、1、2番が先頭チーム、3、4番がリンクチームの場合、2つのチームの能力値は次のようになります.
スタートチーム:S 12+S 21=1+4=5
リンクチーム:S 34+S 43=2+5=7
1、3番がスタートチーム、2、4番がリンクチームの場合、両チームの能力値は以下のようになります.
ホームチーム:S 13+S 31=2+7=9
リンクチーム:S 24+S 42=6+4=10
サッカーを面白くするために、スタートチームの能力値とリンクチームの能力値の差を最小限に抑えたい.上記の例のように、1、4が開始グループ、2、3がリンクグループの場合、開始グループのコンピテンシー値は6、リンクグループのコンピテンシー値は6、差異は0であり、この値は最小である.

入力
第1行はN(4≦N≦20,Nは偶数)を与える.2行目からN行Sを与える.各行はN個の数字で構成され、i行のj番号はSijである.Siiは常に0であり、残りのSijは1以上、100以下の整数である.

しゅつりょく
最初の行は、開始グループとリンクグループのコンピテンシー値の差の最大値を出力します.

方法

Brate Force問題でチームを構成できるすべての状況の数をDFSとし,その差が最小の場合を求める.

問題を解く

import java.io.*;
import java.util.StringTokenizer;

public class Baek_j_14889 {
    public static int min = Integer.MAX_VALUE;
    public static int input[][];
    public static int N;
    public static int check[];
    public static void main(String[] args) throws IOException{

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());

        input = new int[N][N];
        check = new int[N];

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

        dfs(0,0);

        System.out.println(min);


    }
    public static void dfs(int ind, int dep){

        // 2개의 그룹이라 팀의 인원수는 전체 인원의 2분의 1이다.
        if(dep == (N/2)){
            // 팁의 인원수가 만족되면 두 그룹의 차이의 최솟값을 찾기 위해 Min 함수 호출
            Min();
            return;
        }

        for(int i = ind; i < N; i++){
            if(check[i] == 0){
                check[i] = 1;

                // 나올 수 있는 모든 경우의 수를 1 로 만든다.
                // (팀을 구성할때 ,1 과 0를 기준으로 팀을 구성할 수 있다)
                dfs(i+1,dep+1);
                check[i] = 0;
            }
        }
    }

    public static void Min(){

        int s_Group = 0;
        int l_Group = 0;

        for(int i  = 0 ; i < N-1; i++){
            for(int j = i+1; j < N; j++){
                // vi가 1 dl면 Start 팀
                if(check[i] == 1 && check[j] == 1){
                    s_Group += input[i][j];
                    s_Group += input[j][i];
                }
                // vi가 0 이면 Link 팀
                else if(check[i] == 0 && check[j] == 0){
                    l_Group += input[i][j];
                    l_Group += input[j][i];
                }
            }
        }

        // 두 그룹의 차이
        int temp = Math.abs(s_Group - l_Group);

        // 차이 값이 0이면 더이상 프로그램을 수행할 필요가 없다
        // 바로 프로그램 종료
        if(temp == 0){
            System.out.print(0);

            System.exit(0);
        }
        // 아니면 min과 temp중 작은값을 min에 할당

        min = Math.min(min,temp);

    }
}

💡 問題解決過程の感受点

私にとってはかなり難しい問題です.DFSを最初に実装する場合、1つのチームメンバーが構成されると、別のチームが自動的に構成されるので、2次元配列として実装し、同じ最小値を求めようとすると、コードが非常に複雑になります.そこで,最小値を求める関数を別に作成し,チームメンバーの和だけを要求すればよいと考えたので,配列を使用する必要はないので,上記の実装を試みた.

体現的には、思ったより難しい問題ではなく、少し疎い問題タイプのようです.だから、私はもっと、もっと多くの問題に触れるべきだと思います.