[백준] 14889번 스타트와 링크 순열로 풀어보기 : Programming Story

1. 문제

1) 링크

www.acmicpc.net/problem/14889

2) 문제

오늘은 스타트링크에 다니는 사람들이 모여서 축구를 해보려고 한다. 축구는 평일 오후에 하고 의무 참석도 아니다. 축구를 하기 위해 모인 사람은 총 N명이고 신기하게도 N은 짝수이다. 이제 N/2명으로 이루어진 스타트 팀과 링크 팀으로 사람들을 나눠야 한다.

BOJ를 운영하는 회사 답게 사람에게 번호를 1부터 N까지로 배정했고, 아래와 같은 능력치를 조사했다. 능력치 Sij는 i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치이다. 팀의 능력치는 팀에 속한 모든 쌍의 능력치 Sij의 합이다. Sij는 Sji와 다를 수도 있으며, i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치는 Sij와 Sji이다.

축구를 재미있게 하기 위해서 스타트 팀의 능력치와 링크 팀의 능력치의 차이를 최소로 하려고 한다.

3) 입력

첫째 줄에 N(4 ≤ N ≤ 20, N은 짝수)이 주어진다. 둘째 줄부터 N개의 줄에 S가 주어진다. 각 줄은 N개의 수로 이루어져 있고, i번 줄의 j번째 수는 Sij 이다. Sii는 항상 0이고, 나머지 Sij는 1보다 크거나 같고, 100보다 작거나 같은 정수이다.

4) 출력

첫째 줄에 스타트 팀과 링크 팀의 능력치의 차이의 최솟값을 출력한다.

더 자세한 문제의 제한을 볼려면 위의 백준 링크를 클릭해보자.

2. 다른 방식으로 풀기

https://www.programmingstory.com/2024/02/14889.html

https://www.programmingstory.com/2024/02/14889-with-method.html

사실 이 문제는 굉장히 다양한 방법으로 풀 수 있는 문제여서 전 포스팅에서도 여러 가지 방법으로 풀어봤었다. 다른 방법으로도 풀고 싶은 사람들은 위의 링크를 클릭해보면 된다.

3. 순열로 풀어보기

이번에는 순열을 활용해서 풀 수 있는 또 다른 방법에 대해서 포스팅해보려고 한다.

이 문제가 순열을 활용해서 풀 수 있는 이유는 두개의 팀을 n/2명으로 각각 나눈다고 문제에서 명시가 되어있기 때문이다. 만약 몇명으로 나눈다라는 말이 없었다면 순열로 풀 수 있다.

단 두 팀으로 나누어야 하는 것이기 때문에 n명의 크기만큼의 배열을 준비하고 1번 팀이라면 0으로 표시하고, 2번 팀이라면 1로 표시해준다. 즉 0 과 1의 조합으로 된 순열이라고 할 수 있는 것이고 이것을 오름차순의 순열로 여러 가지 조합을 만들어주면 n/2명씩 두 팀을 나누는 모든 경우의 수를 다룰 수 있게 되는 것이다.

그래서 만약 해당 배열이 0이라면 첫 번째 팀 배열에 넣어주고, 1이라면 두 번째 팀 배열에 넣어주는 식이다. 이런 식으로 순열 함수를 호출해 계속 팀의 조합을 다르게 한다. 이후에는 전에 한 것처럼 두 팀의 능력차이를 계산해준다.

이번에는 조금 다르게 능력차이를 모두 ArrayList에다가 넣어주고 그것의 최솟값을 바로 한번에 출력해주는 형식으로 진행했다. 이렇게 하면 새로운 ArrayList가 하나 더 필요하다는 단점은 있지만 값이 나올때 마다 지속적으로 비교하지 않아도 된다는 장점은 있다.

4. 코드

아래는 전체코드이다.

import java.util.*;

public class Main{
    public static boolean next_permutation(int a[]){
        int i=a.length-1;
        while(i>0 && a[i-1]>=a[i]){
            i--;
        }
        if (i<=0) return false;
        int j=a.length-1;
        while(a[i-1]>=a[j]){
            j--;
        }
        int tmp=a[i-1];
        a[i-1]=a[j];
        a[j]=tmp;
        j=a.length-1;
        while(i<j){
            tmp=a[i];
            a[i]=a[j];
            a[j]=tmp;
            i++;
            j--;
        }
        return true;
    }
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int ability[][]=new int[n][n];
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                ability[i][j]=sc.nextInt();
            }
        }
        int team[]=new int[n];
        for(int i=0; i<n/2; i++){
            team[i]=1;
        }
        Arrays.sort(team);
        ArrayList<Integer> diff=new ArrayList<>();
        do{
            ArrayList<Integer> first=new ArrayList<>();
            ArrayList<Integer> second=new ArrayList<>();
            for(int i=0; i<n; i++){
                if (team[i]==0){
                    first.add(i);
                }
                else{
                    second.add(i);
                }
            }
            
            int f_sum=0;
            int s_sum=0;
            for(int i=0; i<n/2; i++){
                for(int j=0; j<n/2; j++){
                    if (i==j) continue;
                    f_sum+=ability[first.get(i)][first.get(j)];
                    s_sum+=ability[second.get(i)][second.get(j)];
                }
            }
            diff.add(Math.abs(f_sum-s_sum));
        }while(next_permutation(team));
        System.out.println(Collections.min(diff));
    }
}

순열로 푼 부분 이외에는 다른 부분은 전의 포스팅과 거의 유사한 것을 알 수 있다.