BOJ14889_스타트와 링크

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

문제정리

1. 축구를 하기 위해 모인 사람은 총 N명이고 짝수이다

2. N/2로 나눠서 스타트팀과 링크 팀으로 나눈다

3. 사람에게 번호를 1부터 N까지 배정 후 사람마다 능력치를 부여 한다

4. Sij는 i번 사람과 j번 사람이 같은 팀에 속했을 때 팀에 더해지는 능력치 이다

5. 팀의 능력치는 팀에 속한 모든 쌍의 능력치의 합이다

6. Sij는 Sji와 다를 수 있으며 , i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는

능력치는 Sij + Sji이다

7. 두팀의 능력치의 차이의 최솟값을 출력

문제issue

딱히 없었음

해결흐름

1. 크기가 N인 일차원 배열을 생성해서 1 2 3 4 ... N 까지 배열에 넣는다

2. N/2 개수의 조합을 구성한다

3. 위 조합에서 N/2 Comb 2를 구한다

4. q(DeQue사용)의 양쪽 끝의 차이를 구하면 된다 , q의 처음 팀 : 1,2,3 , q의 마지막 팀 : 4,5,6

이런식으로 q에 저장되기 때문에 양쪽 끝의 차이를 구해서 최솟값을 갱신한다.

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
 
public class Main {
    private static int N;
    private static int[][] map;
    private static int[] arr;
    private static int[] comb_arr;
    private static boolean[] arr_visited;
    private static boolean[] comb_visited;
    private static int[] comb_arr2;
    private static int sum;
    private static Deque<Integer> q;
 
    public static void main(String[] args) throws Exception {
        // input
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine().trim());
        map = new int[N+1][N+1];
        arr = new int[N];
        arr_visited = new boolean[N];
        comb_arr = new int[N/2];
        comb_visited = new boolean[N/2];
        comb_arr2 = new int[2];
        q = new LinkedList<Integer>();
        sum = 0;
        for (int i = 1; i <= N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine().trim(), " ");
            for (int j = 1; j <= N; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        int number = 1;
        for (int i = 0; i < N; i++) {
            arr[i] = number++;
        }
        // start
        comb(0,0);
        int min = Integer.MAX_VALUE;
        int cha = 0;
        while(!q.isEmpty()) {
            int number1 = q.pop();
            int number2 = q.removeLast();
            cha = Math.abs(number1 - number2);
            if(min > cha)
                min = cha;
        }
        System.out.println(min);
        
    } // end of main
 
    // N Comb N/2를 구하는 comb
    private static void comb(int len, int t) {
        if(len == N/2) {
            sum = 0;
            comb2(0,0);
            q.add(sum);
            return;
        }
        for (int i = t; i < arr.length; i++) {
            if(!arr_visited[i]) {
                comb_arr[len] = arr[i];
                arr_visited[len] = true;
                comb(len + 1, i + 1);
                arr_visited[len] = false;
            }
        }
    }
 
    // N/2 Comb 2를 구하는 comb2
    private static void comb2(int len, int t) {
        if(len == 2) {
            solve();
            return;
        }
        for (int i = t; i < comb_arr.length; i++) {
            if(!comb_visited[i]) {
                comb_arr2[len] = comb_arr[i];
                comb_visited[len] = true;
                comb2(len + 1, i + 1);
                comb_visited[len] = false;
            }
        }
    }
 
    private static void solve() {
        // comb_arr2를 사용
        sum += map[comb_arr2[0]][comb_arr2[1]];
        sum += map[comb_arr2[1]][comb_arr2[0]];
    }
} // end of class