코드트리 [자바 java] 조삼모사

https://www.codetree.ai/problems/three-at-dawn-and-four-at-dusk?utm_source=clipboard&utm_medium=text 

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

위와 같은 업무가 주어졌을 때 아침과 저녁에 할 일의 분배가 최대한 비슷하게 만드는 문제이다.

나는 백트래킹을 이용한 브루트포스를 사용했다.

우선, 아침에 할 일과 저녁에 할 일을 묶는데 한번 사용하고, 아침과 저녁에 할 업무를 전부 더해서 값을 구하는데 한번 더 사용했다.

또한 거의 모든 배열은 사용하기 용이하게 하기 위해서 전역변수를 사용했다.

 

import java.util.*;
import java.io.*;
import java.math.*;

public class Main {
    static int n;
    static int[][] arr;
    static int[]  gr1;
    static int[]  gr2;
    static int[] vis;
    static int min = 1000000000; //fail뜨면 생각하기
    static int[] two = new int[2];

    //2개씩 순열구하기
    static void two(int k, int num){
        if(k ==2){
            sum();
        }
        else{
            for(int i = num;i<n/2;i++){
                two[k] = i;
                two(k+1, i+1);
            }
        }

    }

    static void sum(){
      // System.out.printf("%d %d\n", gr1[two[0]], gr1[two[1]]);
        sum1 += (arr[gr1[two[0]]][gr1[two[1]]] + arr[gr1[two[1]]][gr1[two[0]]]) ;
        sum2 += (arr[gr2[two[0]]][gr2[two[1]]] + arr[gr2[two[1]]][gr2[two[0]]]) ;
    }

    static int sum1;
    static int sum2;

//그룹에 있는 것들 노동 합 구하기
    static void hap(){
        sum1 = 0;
        sum2 = 0;
        int num = 0;
        for(int i = 0;i<n;i++){
            if(vis[i] == 0){
                
                gr2[num] = i;
                num++;
            }
        }
       
        two(0,0);
        //System.out.printf("%d %d\n", sum1,sum2);
        min = Math.min(min, Math.abs(sum1-sum2));

    }

//그룹만들기
    static void make(int k, int num){
        if(k == n/2){
            hap();
        }
        else{
            for(int i = num;i<n;i++){
                vis[i] = 1;
                gr1[k] = i;
                make(k+1, i+1);
                vis[i] = 0;

            }
        }
    }

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

        arr = new int[n][n];
        StringTokenizer st;

        for(int i =0 ;i<n;i++){
            st = new StringTokenizer(br.readLine());
            for(int j = 0;j<n;j++){
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        gr1 = new int[n/2];
        gr2 = new int[n/2];
        vis = new int[n];

        make(0,0);

        System.out.println(min);
        

    }
}