백준 14889 스타트와 링크 c++ [컴공과고씨]

 

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

14889번: 스타트와 링크

 

이 문제의 핵심은 두 가지로 볼 수 있다. 첫 번째는 팀을 어떤 식으로 구성하는 가. 두 번째는 구성한 팀에서 능력치를 구해 전 팀과 비교. 팀을 구성하는 방법은 중복을 고려해주어야 한다. 

 

팀을 구성하는 방법

- 먼저 한 팀의 인원은 n/2이다. n이 4라고 할 때 한 팀의 인원은 2명

- 01 02 03 12 13 23 이런식으로 구성할 것이다.

	for (int i = start; i < n;i++){ // 중복 고려해서 i=start
            if(!visit[i]){
                visit[i] = true;
                fc(i+1, cnt + 1);
                visit[i] = false;
            }
        }

 중요한 것은 i=start이다. void fc(int start, int cnt)는 재귀 함수로 위에 부분을 가지고 있다.

만약 i를 0부터 라고 하면 00 01 02 03 10 11 12 ... 해서 팀을 구성할 수 없는 애들을 계속 구성하여 연산 시간이 많아지게 된다. 그렇기 때문에 이미 0번째를 팀으로 구성했다면 다음 선수는 0이 될수 없음으로 검사할 필요가 없다.

 

 

이렇게 팀이 구성되면 아까 팀을 구성할 때 visit에 true라고 표시를 해두었기 때문에 visit가 true인 선수들은 1번팀

false라면 2번팀으로 넣어준다. 그 후 팀 별로 능력치를 계산해준다. 문제에서 주어진 표를 이용해서 구해주면 된다.

그 후 두 팀의 능력치의 차를 구한 후 절댓값을 취해준 후 전에 팀 능력치 차와 비교하여 더 작은 값을 저장하면 된다.

 

전체적인 알고리즘은 재귀 함수를 백트래킹을 이용한 것이다.

 

 

전체코드

#include <iostream>
#include <cmath>
using namespace std;
int n, num;
int map[22][22];
int team1[12];
int team2[12];
bool visit[12] = {0};
int ans = -1;
void fc(int start, int cnt){
    if(cnt == num){
        int temp1 = 0;
        int temp2 = 0;
        for (int i = 0; i < n; i++){
            if(visit[i]){
                team1[temp1] = i; // 1번팀에 넣어줌
                temp1++;
            }else{
                team2[temp2] = i; // 2번 팀에 넣어줌
                temp2++;
            }
        }
        temp1 = 0;
        temp2 = 0;
        for (int j = 0; j < num - 1; j++)
        {
            for (int k = j + 1; k < num; k++)
            {
                temp1 += map[team1[j]][team1[k]] + map[team1[k]][team1[j]]; // 1번 팀 능력치
                temp2 += map[team2[j]][team2[k]] + map[team2[k]][team2[j]]; // 2번 팀 능력치
            }
        }
        int sub = abs(temp1 - temp2); // 절댓값
        if(ans > sub || ans == -1){ 
            // 더 작은 값 저장 -1일때는 처음일 경우
            ans = sub;
        }
    }else{ // 팀 구성하기
        for (int i = start; i < n;i++){ // 중복 고려해서 i=start
            if(!visit[i]){
                visit[i] = true;
                fc(i+1, cnt + 1);
                visit[i] = false;
            }
        }
    }
    
}
 
int main(){
    ios::sync_with_stdio(false);
    cin >>n;
    num = n / 2;
    for (int i = 0; i < n; i++){
        for (int j = 0; j < n; j++){
            cin >> map[i][j];
        }
    }
    fc(0, 0);
    cout << ans;
    return 0;
} // 1h

체감난이도	걸린시간	참고	사용 알고리즘
중	1h	x	백트래킹(back tracking)