[GDSC Week3-1] 백준 1489번:: 스타트와 링크 (C++)

 

* 생각한 아이디어 및 문제 풀이

두 팀의 능력치를 구하고, 그 차이의 최솟값을 구하는 문제이다. 
백트레킹으로 N명을 N/2명으로 나누어 각각 두 팀으로 나눠서 vector에 push해준다.
각각의 능력치를 return하는 getStat 함수를 통해 능력치를 계산하였다.
답은 두 팀 능력치 차이의 최솟값이다.

 

* 코드

#include <iostream>
#include <vector>
using namespace std;

int n;
int team[20][20];
int check[20];
int ans = 0x7f7f7f7f; //초기화

int getStat(vector<int> oneTeam){
    int stat = 0;
    int size = oneTeam.size();
    for(int i=0; i<size; i++){
        for(int j=0; j<size; j++){
            if(i!=j){
                stat += team[oneTeam[i]][oneTeam[j]];
            }
        }
    }
    return stat;
}   

void backTracking(int depth, int index){
    if(depth == n/2) {
        vector<int> aTeam;
        vector<int> bTeam;
        for(int i=0; i<n; i++) {
            if(check[i]) aTeam.push_back(i);
            else bTeam.push_back(i);
        }
        
        int aStat = getStat(aTeam);
        int bStat = getStat(bTeam);
        ans = min(ans,abs(aStat - bStat));
        return;
    }

    for(int i=index; i<n; i++){
        if(check[i]) continue;
        check[i] = 1;
        backTracking(depth+1,i+1);
        check[i] = 0;
    }
}

int main(){
    cin >> n;
    for(int i=0; i<n; i++)
        for(int j=0; j<n; j++) 
            cin >> team[i][j];
    
    backTracking(0, 0);
    cout << ans << '\n';
}

 

* 회고

 

 

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

14889번: 스타트와 링크

https://codecollector.tistory.com/776

(C++) - 백준(BOJ) 14889번 : 스타트와 링크 답