[백준] 14889번 스타트와 링크

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

문제

문제 이해

N명의 사람이 들어옴, N은 항상 짝수이고, N/2명씩 각각 두 팀을 만든다.
그리고 누군가와 같은 팀이 되면, 특정 능력치를 얻는다.
각 팀의 구성원들의 능력치를 다 합하면 팀의 능력치가 된다.
두 팀의 능력치의 차이가 가장 작은 수를 구하는 문제.

문제 접근

1. N/2 만큼의 선수 나누기
2. 구성한 팀으로 팀 능력치 구하기
3. 최소값 구하기

선수를 나눌 때는 dfs를 사용하여, N/2만큼 채워질 때까지 진행하였고, N/2 채워지면, 각 선수를 두 팀으로 나눴다.
입력으로 받은 표를 사용하여, 각 팀의 능력치를 얻어냈다.
최솟값은 해당 값이 계산되기 전에 최솟값과 현재 값을 비교하여, 현재의 최솟값을 구하였다.

코드 구현(c++)

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

using namespace std;

int ability[20][20];
int n;
vector<int> check_num;
int check[20];
int result = 999999;
vector<int> team_start, team_link;


void cal(){
    int start = 0;
    int link = 0;
    for(int i = 0 ; i < n/2 ; i++){
        for(int j = 0 ; j < n/2 ; j++){
            start += ability[team_start[i]][team_start[j]];
            link += ability[team_link[i]][team_link[j]];
        }
    }
    team_start.clear();
    team_link.clear();
    int temp = abs(start - link);
    if(result > temp) result = temp;
}

void make_team(){
    for(int i = 0 ; i < n ; i++){
        if(check[i]) team_start.push_back(i);
        else team_link.push_back(i);
    }
}
void dfs(int t , int count){
    if(count == n/2){
        make_team();
        cal(); 
    }
    else{
        for(int i = t; i < n ; i++){
            if(!check[i]){
                check[i] = true;
                dfs(i+1 ,count+1);
                check[i] = false;
            }
        }
    }
    return;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    cin >> n;
    for(int i = 0 ; i < n ; i++){
        for(int j = 0 ; j < n ; j++){
            cin >> ability[i][j];
        }
    }
    dfs(0,0);

    cout << result << "\n";
}

평가

정답이 나오고, 실행이 되게 구현한 것은 금방하였다. 하지만, 계속 시간초과가 나왔다. 그래서 여러 방법으로 코드를 바꿨다. 결국 dfs에서 다음으로 검사할 인덱스가 어디인지 알려주는 인자를 추가함으로, 시간 초과를 해결했다.