[알고리즘] 백준 14889번 스타트와 링크 Java 자바

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

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

    static int N;
    static boolean chk[];
    static int [][] stats;
    static long result=Integer.MAX_VALUE;
    public static void main(String[] args) throws Exception {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        N=Integer.parseInt(br.readLine());
        stats=new int[N][N];//능력치
        for(int i=0;i<N;i++){
            StringTokenizer strToken=new StringTokenizer(br.readLine(), " ");
            for(int j=0;j<N;j++){
                stats[i][j]=Integer.parseInt(strToken.nextToken());
            }
        }
        chk=new boolean[N];
        dfs(0,0);
        System.out.println(result);
    }
    
    public static void dfs(int depth,int start){
        long starStat = 0, linkStat =0;
        if(depth==N/2){
            for(int i=0;i<N;i++){
                if(chk[i]){
                    starStat+=starStatAdd(i);
                }else{
                    linkStat+=linkStatADD(i);
                }
            }
            long diff=starStat-linkStat;
            diff=Math.abs(diff);
            if(diff==0){
                System.out.println(0);
                System.exit(0);
            }
            if(result>diff) {
                result=diff;
            }
            return;
        }
        for(int i=start;i<N;i++){
            chk[i]=true;
            dfs(depth+1,i+1);
            chk[i]=false;
        }
    }

    public static long starStatAdd(int i){
        long result=0;
        for(int j=0;j<N;j++){
            if(chk[j])
            result+=stats[i][j];
        }
        return result;
    }

    public static long linkStatADD(int i){
        long result=0;
        for(int j=0;j<N;j++){
            if(!chk[j])
                result+=stats[i][j];
        }
        return result;
    }

}

문제풀이 : 자바 백트레킹을 이용하여 푼다.

백트레킹 알고리즘 문제 중 백준6603번 로또 코드를 이용하여 풀었습니다.  

백준6603번 로또 코드 보러가기

[알고리즘] 백준 6603번 로또 Java

순차적으로 코드 해보면 쉽게 풀 수 있습니다.

1. 변수 선언 및 초기화

2. 두개의 팀으로 나눈다.(모든 경우의 수로 구한다. -백트레킹기법)

2. 각 팀의 능력치를 구한다.

3. 능력치 절대값으로 비교하여 최소값을 구한다.