[백준 알고리즘/BOJ/C++] 14889 스타트와 링크

능력치를 팀별로 합한 뒤 두 팀의 능력치를 비교한다

재밌는 축구를 위해 모든 경우의 수를 따져 두 팀의 능력치 차이가 가장 적은 경우를 찾아야 한다

​

핵심은

(1) 팀을 이룰 수 있는 모든 경우 (코드에서 dfs 함수)

(2) 팀 능력치 구하고 비교 (코드에서 update 함수)

 

 

#include <iostream>
using namespace std;
 
int n, arr[20][20];
int team1[10], team2[10];
int pick[20], result = 0x7fffffff; //result에 변수가 가질 수 있는 최댓값 넣어놓기
 
void update() {
    int team1_size = 0, team2_size = 0;
 
    for (int i = 0; i < n; i++) { //팀 분류하기. pick 되지 않은 애들을 team1으로
        if (pick[i] == 0)
            team1[team1_size++] = i;
        else
            team2[team2_size++] = i;
    }
 
    int sum1 = 0, sum2 = 0;
    for (int i = 0; i < n / 2; i++) { //능력치 합 구하기
        for (int j = i + 1; j < n / 2; j++) {
            sum1 += arr[team1[i]][team1[j]] + arr[team1[j]][team1[i]];
            sum2 += arr[team2[i]][team2[j]] + arr[team2[j]][team2[i]];
        }
    }
 
    if (result > abs(sum1 - sum2))
        result = abs(sum1 - sum2);
}
 
void dfs(int cur, int pick_cnt) {
    if (pick_cnt == (n / 2)) { //n의 절반이 한 팀으로 분류 됐으니 차이 구하기
        update();
        return;
    }
 
    for (int i = cur; i < n; i++) { //팀 뽑기
        pick[i] = 1;
        dfs(i + 1, pick_cnt + 1);
        pick[i] = 0;
    }
}
 
int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
 
    cin >> n;
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++)
            cin >> arr[i][j];
    }
 
    dfs(0, 0);
 
    cout << result;
}

 

나중에 다시 풀어보고 싶은 문제