ALGORITHM

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

연듀 2022. 12. 12. 19:59

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

 

14889번: 스타트와 링크

예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다.

www.acmicpc.net

 

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

public class Main{
    public static int[][] arr;
    public static boolean[] visited;
    public static int n;

    public static int min = Integer.MAX_VALUE;

    public static void dfs(int cnt, int s){ // 조합
        if(cnt==n/2){

            int start = 0;
            int link = 0;

            for(int i=1; i<n; i++){
                for(int j=i+1; j<=n; j++){
                    if(visited[i] && visited[j]){ // 두 사람이 true면 스타트팀
                        start += arr[i][j] + arr[j][i];
                    }
                    else if(!visited[i] && !visited[j]){ // 두 사람이 false면 링크팀
                        link += arr[i][j] + arr[j][i];
                    }
                }
            }
            int gap = Math.abs(start-link); // 두 팀의 점수 차이

            min = Math.min(min, gap);
            return;
        }

        for(int i=s; i<=n; i++){ // 중복된 수열이 나오지 않도록 오름차순으로 하기 위해 s부터 시작
            if(visited[i]) continue;

            visited[i] = true;
            dfs(cnt+1, i+1); // 카운트 증가, i증가(오름차순 위해)
            visited[i] = false;

        }
    }
    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+1][n+1];
        visited = new boolean[n+1];

        StringTokenizer st;

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

        dfs(0, 1);

        System.out.println(min);
    }
}

'ALGORITHM' 카테고리의 다른 글

[JAVA] 백준 2529번- 부등호  (0) 2022.12.14
[JAVA] 백준 1759번- 암호 만들기  (0) 2022.12.14
[JAVA] 백준 14501번- 퇴사  (0) 2022.12.12
[JAVA] 백준 2668번- 숫자고르기  (0) 2022.12.01
[JAVA] 백준 10971번- 외판원 순회2  (0) 2022.11.30