[BOJ] 스타트와 링크

[문제]

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

14889번: 스타트와 링크

[풀이]

 

14889

맞았습니다!!

1988 kb

32 ms

C++14 / 수정

1280

 

1) 재귀함수 호출로 팀을 나누는 전형적인 문제이다. 

 

2) n명의 직원이 있고 n/2 인원만큼 두 팀으로 나눴을 때 팀역량의 합의 차이가 최소가 되게 해야한다. 

 

3) dfs(현재까지 나눈 인원의 수, 현재 나눌 인원의 인덱스 ) 로 두고 현재까지 나눈 인원의 수가 n/2가 될 때까지 재귀 호출한다. 

 

4) visited 배열을 사용해서 현재 나눈 팀원과 아닌 팀원을 구별한다. 

 

5) divideTeam() 에서는 이제 A팀과 B팀을 지정한다. 

 

6) A팀과 B팀으로 나눠지면 각각 팀원들의 역량의 합을 구한 후 그 차이의 최소값을 구한다. 

 

---

#include <iostream>
#include <vector>
#include <cstring>
 
using namespace std;
 
//풀이 14분 
int n, map[20][20], ans = 987654321;
bool visited[20];
 
void divideTeam() {
    int nA = 0, nB = 0;
    int A[n/2+2], B[n/2+1];
    memset(A, 0, sizeof(A));
    memset(B, 0, sizeof(B));
    
    for (int i = 0; i < n; i++) {
        if (visited[i]) {
            A[nA++] = i; 
        }
        else {
            B[nB++] = i;
        }
    }
 
    //능력차 차이를 구한다. 
    int resA = 0, resB = 0;
 
    for (int i = 0; i < n/2; i++) {
        for (int j = 0; j < n/2; j++) {
            if (i == j) continue;
            resA += map[A[i]][A[j]];
        }
    }
    for (int i = 0; i < n/2; i++) {
        for (int j = 0; j < n/2; j++) {
            if (i == j) continue;
            resB += map[B[i]][B[j]];
        }
    }
 
    if (abs(resA - resB) < ans) {
        ans = abs(resA - resB);
    
    }
}
void dfs(int cnt, int cur) {
    if (cnt == n/2) {
        //팀 모두 나눔 
        divideTeam();
        return;
    }
    if (cur >= n) return;
 
    for (int i = cur; i < n; i++) {
        if (!visited[i]) {
            visited[i] = true;
            dfs(cnt+1, i+1);
            visited[i] = false;
        }
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    cin >> n;
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> map[i][j];
        }
    }
    //input 
 
    dfs(0,0);
 
    cout << ans << '\n';
    return 0;
}