본문 바로가기

개발/알고리즘

백준 알고리즘 14889

입력 : 축구 인원 N과 능력치 테이블

출력 : 팀을 구성하는 경우의 수 중에서 두 팀 간의 능력치차이가 제일 적을 경우의 능력치 차이 값

 

풀이

1. 한 팀을 만드는 모든 경우의 수를 재귀함수를 통해 구한다.
    -> 재귀실행 1회 당 선수 1명 영입
    -
> 재귀실행 N/2회 실행시(기저조건), teamA에 인원이 N/2명이면 팀 능력치 계산
    -> teamA에 없는 선수를 teamB에 영입해 능력치 계산 후 차이를 계산해 리턴

2. 중복을 피하기 위해 i번 선수 영입 후 다음 영입 선수는 i+1이상의 선수 중에서 선택

 

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include <iostream>
#include <cmath>
#include <vector>
 
using namespace std;
 
int table[22][22];
bool teamCache[22];
vector<int> teamA;
int n;
 
int getTeamScore(){
    int scoreA = 0;
    int scoreB = 0;
    vector<int> teamB;
 
    for(int i=0; i<n; i++)
        if(!teamCache[i])
            teamB.push_back(i);
    
    for(int i=0; i<n/2; i++){
        for(int j=i+1; j<n/2; j++){
            scoreA += table[teamA[i]][teamA[j]];
            scoreA += table[teamA[j]][teamA[i]];
            
            scoreB += table[teamB[i]][teamB[j]];
            scoreB += table[teamB[j]][teamB[i]];
        }
    }
    
    return abs(scoreA-scoreB);
}
 
int matching(int teamNum, int bottom){
    if(teamNum == n/2){
        if(teamA.size() != n/2)
            return 10000000;
        else 
            return getTeamScore();
    }
    int result = 10000000;
    
    for(int i=bottom; i<n; i++){
        int temp = 0;
        teamA.push_back(i);
        teamCache[i] = true;
 
        temp = matching(teamNum + 1, i+1);
        if(result > temp)
            result = temp;
 
        teamA.pop_back();
        teamCache[i] = false;
    }
    
    return result;
}
 
int main() {
    cin>>n;
    
    for(int i=0; i<n; i++)
        for(int j=0; j<n; j++)
            cin>>table[i][j];
    
    cout<<matching(0,0)<<endl;
    
    return 0;
}
 
cs

 

'개발 > 알고리즘' 카테고리의 다른 글

백준 알고리즘 14891  (0) 2019.02.20
백준 알고리즘 1673  (0) 2019.02.20
백준 알고리즘 14500  (0) 2019.02.19
백준 알고리즘 14501  (0) 2019.02.16
백준 알고리즘 13458  (0) 2019.02.16