[백준(BOJ)] 14889번 스타트와 링크 C++

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

14889번: 스타트와 링크

 

 

어떤 문제인가?

1부터 짝수인 n까지의 사람이 있다.

팀을 n/2, n/2명으로 두 팀으로 나눈다.

이때, 각 팀원들의 능력치를 합산해서 두 팀의 최종 능력치를 구한다.

그다음, 두 팀의 최종 능력치가 최솟값을 구하면 된다.

접근 방법

팀원들을 나누는 방법은 조합을 사용해서 가능한 모든 경우의 수를 탐색하면 된다.

n명 중 n/2명을 뽑으면  나머지 인원들이 다른 팀이 되기 때문이다.

 

int n;
int arr[20 + 1][20 + 1];
int minNum = 10001;

n이 최대 20까지 입력 가능하니 2차원 배열의 크기를 21 * 21로 해주었다.

minNum은 두 팀의 차이를 저장할 것이다.

최악의 경우 한 팀의 10명이 모두 100이고 다른 팀의 10명이 모두 1일 경우 차이가 최대가 된다.

그래서 대충 10001로 지정해주었다.

 

cin >> n;

for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
        cin >> arr[i][j];
    }
}

2차원 배열의 값을 입력받는다.

 

vector<int> v;

for (int i = 1; i <= n; i++) {
    v.push_back(i);
}

1부터 n까지의 사람들의 번호를 v 벡터에 저장한다

 

 

 

vector<int> temp;

int k = n / 2;

for (int i = 0; i < k; i++) {
    temp.push_back(1);
}

for (int i = 0; i < v.size() - k; i++) {
    temp.push_back(0);
}

sort(temp.begin(), temp.end());

조합을 사용하기 위한 temp벡터이다.

k가 뽑는 수이기 때문에 n/2로 초기화해준다. 

 

 

 

그리고 next_permutaion함수를 통해 조합의 모든 경우의 수를 탐색할 것이다.

do {
    vector<int> start;
    vector<int> link;
    int startTotal = 0;
    int linkTotal = 0;

    for (int i = 0; i < temp.size(); i++) {
        if (temp[i] == 1) {
            start.push_back(v[i]);
        } else {
            link.push_back(v[i]);
        }
    }

    for (int i = 0; i < start.size(); i++) {
        for (int j = i + 1; j < start.size(); j++) {
            startTotal += arr[start[i]][start[j]];
            startTotal += arr[start[j]][start[i]];
        }
    }

    for (int i = 0; i < link.size(); i++) {
        for (int j = i + 1; j < link.size(); j++) {
            linkTotal += arr[link[i]][link[j]];
            linkTotal += arr[link[j]][link[i]];
        }
    }

    int diff = abs(linkTotal - startTotal);
    if(diff < minNum){
        minNum = diff;
    }
    if(minNum==0){
        break;
    }

} while (next_permutation(temp.begin(), temp.end()));

스타트팀과 링크팀 팀원의 숫자를 저장할 벡터를 선언하고 각 팀의 능력치를 저장할 변수를 0으로 초기화해준다.

 

이제 조합을 통해 팀을 분류해준다.

temp의 인덱스 값이 1이면 스타트팀, 0이면 링크팀으로 추가해준다.

 

그리고 각 팀의 점수를 이중 for문을 통해 계산해준다.

코드를 보면 이해가 될 것이다.

 

그리고 두 팀의 능력치 차이의 절댓값(diff)과 minNum을 비교한다.

 

만약 diff가 minNum보다 작다면 minNum을 diff로 바꿔준다.

 

하지만 여기서 minNum이 0이라면 가장 작은 차이이니 남은 경우의 수를 더 알아볼 필요가 없으므로 반복문을 탈출한다.

 

cout << minNum;

계산된 두 팀의 능력치 차이의 최솟값을 출력해주면 끝!

 

 

무엇이 어려웠는가?

조합을 사용할 줄 알았다면 문제의 로직 자체에는 큰 어려움이 없었다.

다만 구현하는 부분이 조금 번거로웠다.

 

사실 모든 경우의 수를 다 탐색해볼 필요는 없다.

 

n이 4일 때, 즉 사람이 4명일 경우이다.

 

3 4 
2 4 
2 3 
1 4 
1 3 
1 2 

 

3, 4 일 때는 1, 2가 반대

2, 4 일 때는 1, 3이 반대

.

.

.

보듯이 i번째와 n-i번째가 같은 경우이다.

그래서 nC(n/2)의 값의 반만 탐색하면 된다.

nC(n/2)의 반만큼만 반복하려고 했는데,

nC(n/2)의 값을 따로 구하기 싫었다.

 

시간도 충분하고 n의 크기도 크지 않아서 그냥 모든 경우의 수를 중복되더라고 탐색하기로 했다.

 

 

배운점

완전탐색 재밌다!

모든 경우를 다 봐야하니 특별한 예외처리도 없고 맘에 든다 너!