스타트와 링크_14889

문제 출처 : 스타트와 링크_14889

파라미터 정리

N 총 사람 수(4 ~ 20, 짝수)
Row 팀(스타트) or Col 팀(링크)로 생각하기
Sij i번 사람과 j번 사람 사이에 존재하는 시너지 (1~100)
Sij는 Sji와 다를 수 있음
Sii는 항상 0 (자기 자신과의 시너지를 의미하므로 0)
각 팀의 능력치는 모든 팀원의 시너지를 더한 것
원하는 것 = 모든 경우의 수에서 두 팀 사이의 능력치 차이의 최솟값을 반환

간략한 과정

input_1 N 입력받기
input_2 각 사람들 사이의 능력치 S 입력받기
모든 경우의 수 만들기(방법1 재귀, 방법2 )
각 상황에서 두 팀의 시너지(synergy1, synergy2) 계산하고 차이(sub) 구하기
res = min (res, sub) 비교하기
output 최솟값 res 출력하기

코드

재귀 호출 함수를 이용해서 모든 경우의 수 구현

#include <iostream>
#include <vector>

using namespace std;

#define INF 9845615

int N;
int Map[20][20];
vector<int> start;
vector<int> link;
int res;

int solve(int cnt){
    if(cnt == N){
        if(start.size() == N/2 && link.size() == N/2){
            int s_sum = 0, l_sum = 0;
            for(int i = 0; i < N/2; i++){
                for(int j = i+1; j < N/2; j++){
                    if(i == j) continue;
                    int si = start[i], sj = start[j];
                    int li = link[i], lj = link[j];
                    s_sum += Map[si][sj] + Map[sj][si];
                    l_sum += Map[li][lj] + Map[lj][li];
                }
            }
            res = min(res,abs(s_sum-l_sum));
        }
        return res;
    }
    //모든 경우의 수 만들기
    //cnt번 선수를 start에 넣어주거나 link에 넣어주기
    start.push_back(cnt);
    solve(cnt + 1);
    start.pop_back();
    
    link.push_back(cnt);
    solve(cnt + 1);
    link.pop_back();
    
    return res;
}

int main()
{
    cin >> N;
    for(int i = 0; i < N; i++)
        for(int j = 0; j < N; j++)
            cin >> Map[i][j];
    res = INF;
    cout << solve(0) << endl;
    
    return 0;
}

비트마스킹을 이용해서 구현 (11 00 이면 1은 start 0은 link)

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

using namespace std;

#define INF 9845615

int N;
int Map[20][20];
vector<int> start;
vector<int> link;

int calculate(){//두 팀의 시너지 합 계산하기
    int s_sum = 0, l_sum = 0;
    for(int i = 0 ; i < N/2; i++){
        for(int j = i+1; j < N/2; j++){
            if(i == j) continue;
            int si = start[i], sj = start[j];
            int li = link[i], lj = link[j];
            s_sum += Map[si][sj] + Map[sj][si];
            l_sum += Map[li][lj] + Map[lj][li];
        }
    }
    return abs(s_sum-l_sum);
}

int checkBit(int n){
    int res = 0;
    do{
        if(n & 1) res++;
        n = n >> 1;        
    }while(n>0);

    return res;
}

int solve(){
    int res = INF;
    //모든 경우의 수 만들기
    for(int i = 0; i < (1<<N-1); i++){
        //팀이 반반으로 나누어졌을 때
        if(checkBit(i) == (N/2)){
            start.clear();
            link.clear();
            //1은 start팀에 넣고, 0은 link팀에 넣음
            //마지막 수는 항상 link팀에 넣음
            for(int j = 0; j < N-1; j++){
                if(i & (1<<j)) start.push_back(j);
                else    link.push_back(j);
            }link.push_back(N-1);
            //두 팀의 시너지 차이를 구하고 최솟값 고르기
            res = min(res, calculate());
        }
    }
    
    return res;
}

int main()
{
    cin >> N;
    for(int i = 0; i < N; i++)
        for(int j = 0; j < N; j++)
            cin >> Map[i][j];
    cout << solve() << endl;
    
    return 0;
}