백준 14889 - 스타트와 링크

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

14889번: 스타트와 링크

문제 설명

---

축구를 하기 위해 모인 사람은 총 N명이고 신기하게도 N은 짝수이다. 이제 N/2명으로 이루어진 스타트 팀과 링크 팀으로 사람들을 나눠야 한다. i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치는 Sij와 Sji이다.

N=4이고, S가 아래와 같은 경우

예를 들어, 1, 2번이 스타트 팀, 3, 4번이 링크 팀에 속한 경우에 두 팀의 능력치는 아래와 같다.

- 스타트 팀: S12 + S21 = 1 + 4 = 5

- 링크 팀: S34 + S43 = 2 + 5 = 7

 

1, 3번이 스타트 팀, 2, 4번이 링크 팀에 속하면, 두 팀의 능력치는 아래와 같다.

- 스타트 팀: S13 + S31 = 2 + 7 = 9

- 링크 팀: S24 + S42 = 6 + 4 = 10

 

한 팀에 1, 3, 5가 속했을때 2명씩 추출하는 경우
스타트 팀 = s[1][3] + s[3][1] + s[1][5] + s[5][1] + s[3][5] + s[5][3]

 

스타트 팀의 능력치와 링크 팀의 능력치의 차이를 최소가 되게 하는것이다.

 

 

접근 방법

---

Broute force 와 Dfs를 활용하여 문제를 풀어 보았습니다. 처음부터 모든 팀의 경우의 수를 구하고 스타트 팀, 링크 팀의 차이가 최소가 되게 하면 됩니다. 하지만 이번 문제 풀이에서 저의 풀이를 제외한 다른 분의 풀이 방법 또한 소개 했습니다. 다른 분의 코드 출처는 아래에 적어놓았습니다.~

 

 

코드

---

[재귀]

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;
int n,half;
int count,result1,result2;
int map[21][21];
vector<int>team;
vector<int>ret;
vector<int>ans;
void dfs(int c,int start,vector<int>t){
    if(c==half&&t.size()==half){ 
        result1=0,result2=0;
        ret.clear();
        //스타트 팀의 능력치 합산
        for(int i=0;i<t.size()-1;i++){
            for(int j=i+1;j<t.size();j++) result1 += (map[t[i]][t[j]]+map[t[j]][t[i]]);
        }
        //스타트 팀을 제외한 나머지가 링크 팀
        for(int i=0;i<n;i++){
            int flag=1;
            for(int j=0;j<t.size();j++){
                if(i==t[j]) {flag=0;break;}
            }
            if(flag==1) ret.push_back(i);
        }
		//링크 팀의 능력치 합산
        for(int i=0;i<ret.size()-1;i++){
            for(int j=i+1;j<ret.size();j++) result2 += (map[ret[i]][ret[j]]+map[ret[j]][ret[i]]);
        }
		//두 팀의 차이를 저장
        ans.push_back(abs(result1-result2));
        t.pop_back();
        return;
    }
    //재귀호출
    for(int i=start+1;i<n;i++){
        c++;
        t.push_back(i);
        dfs(c,i,t);
        c--;
        t.pop_back();
    }
    
}
int main(){
    cin>>n;
    //입출력
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){cin>>map[i][j];}
    }
    //팀은 인원수의 절반
    half =n/2;
    for(int i=0;i<n/2;i++){
        int count=1;//인원수가 증감 체크
        team.push_back(i);
        dfs(count,i,team);
        team.pop_back();
    }
    //최소의 값을 출력
    sort(ans.begin(),ans.end());
    cout<<ans[0]<<"\n";
    return 0;
}

[순열]

#include <iostream>
#include <vector>
#include <algorithm>
#define max_int 21
#define max_val 2147483647
using namespace std;

/*
 시간 복잡도: O(nCn/2 + n^2)
 공간 복잡도: O(n^2)
 사용한 알고리즘: 순열(next_permutation)
 사용한 자료구조: 배열, 리스트
 */

int n, a[max_int][max_int];
int start_sum, link_sum, start_first, start_second;
int link_first, link_second, result = max_val;

// 스타트, 링크 팀에 속한 사람들의 번호를 저장할 리스트를 벡터로 생성
vector<int> start, link;

// 최소값 반환
int min(int a, int b){
    return a < b ? a : b;
}

// 절대값 반환
int abs(int a){
    if(a < 0) a = a * -1;
    return a;
}

int main(){
    // 1. 입력
    scanf("%d", &n);
    
    // 2차원 배열에 힘의 정보를 입력받습니다.
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            scanf("%d", &a[i][j]);
        }
    }
    
    // 2. 순열 수행
    // 순열을 저장할 리스트 v를 벡터로 생성합니다.
    vector<int> v;
    for(int i=0; i<n/2; i++) v.push_back(0);
    for(int i=0; i<n/2; i++) v.push_back(1);
    do{
        //스타트팀, 링크팀을 만들고
        vector<int> start, link;
        for(int i=0; i<(int)v.size(); i++){
            // 0일때 스타트팀에 넣어줍니다.
            if(v[i] == 0) start.push_back(i + 1);
            // 1일때 링크팀에 넣어줍니다.
            else link.push_back(i + 1);
        }
        
        start_sum = 0;
        link_sum = 0;
        
        // 2중 for문으로 돌면서 각 팀의 선수를 고릅니다. O(n^2)
        for(int i=0; i<n/2; i++){
            for(int j=i+1; j<n/2; j++){
                if(i == j)continue;
                
                // 1) 스타트팀 2명 골라서
                start_first = start[i];
                start_second = start[j];
                
                // 스타트팀 점수 계산
                start_sum += a[start_first][start_second] + a[start_second][start_first];
                
                // 2) 링크팀 2명 골라서
                link_first = link[i];
                link_second = link[j];
                
                // 링크팀 점수 계산
                link_sum += a[link_first][link_second] + a[link_second][link_first];
            }
        }
        
        // 절대값을 취해주고, 최소값을 갱신해줍니다.
        result = min(result, abs(start_sum - link_sum));
        
    }while(next_permutation(v.begin(), v.end()));
    
    // 3. 출력
    printf("%d\n", result);
}

[비트마스크]

#include <iostream>
#include <vector>
#include <algorithm>
#define max_int 21
#define max_val 2147483647
using namespace std;

/*
 시간 복잡도: O(2^n * n^2)
 공간 복잡도: O(n^2)
 사용한 알고리즘: 비트 마스킹
 사용한 자료구조: 배열, 리스트
 */

int n, a[max_int][max_int], start_sum, link_sum, start_first, start_second, link_first, link_second, result = max_val;

// 스타트, 링크 팀에 속한 사람들의 번호를 저장할 리스트를 벡터로 생성
vector<int> start, link;

// 최소값 반환
int min(int a, int b){
    return a < b ? a : b;
}

// 절대값 반환
int abs(int a){
    if(a < 0) a = a * -1;
    return a;
}

int main(){
    // 1. 입력
    scanf("%d", &n);
    
    // 2차원 배열에 힘의 정보를 입력받습니다.
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            scanf("%d", &a[i][j]);
        }
    }
    
    for(int i=(1 << (n/2 + 1)) - 1; i < (1 << n); i++){
        vector<int> start, link;
        for(int j=0; j < n; j++){
            if((i & (1 << j)) != 0) start.push_back(j+1);
            else link.push_back(j+1);
            
        }
        
        // start, link팀 각각의 크기가 n/2로 딱 절반일때
        if(start.size() == n/2 && link.size() == n/2){
            // 변수 초기화
            start_sum = 0;
            link_sum = 0;
            
            // 2중 for문으로 돌면서 각 팀의 선수를 고릅니다. O(n^2)
            for(int i=0; i<n/2; i++){
                for(int j=i+1; j<n/2; j++){
                    if(i == j)continue;
                    
                    // 1) 스타트팀 2명 골라서
                    start_first = start[i];
                    start_second = start[j];
                    
                    // 스타트팀 점수 계산
                    start_sum += a[start_first][start_second] + a[start_second][start_first];
                    
                    // 2) 링크팀 2명 골라서
                    link_first = link[i];
                    link_second = link[j];
                    
                    // 링크팀 점수 계산
                    link_sum += a[link_first][link_second] + a[link_second][link_first];
                }
            }
            
            // 절대값을 취해주고, 최소값을 갱신해줍니다.
            result = min(result, abs(start_sum - link_sum));
        }
    }
    
    
    // 3. 출력
    printf("%d\n", result);
}

funny algorithm *0*b~

순열, 비트마스크 코드 참고 : https://velog.io/@skyepodium/백준-14889-스타트와-링크