[백준 3980] 선발 명단 (C++)

3980번: 선발 명단

백트래킹

 

인원수가 최대 11명이고 자신이 원하는 포지션 최대 5개 중 하나에 들어갈 수 있으므로 O(5^11 - @)의 시간복잡도가 가능하다고 생각한다. 포지션은 11개인데 11명의 선수가 원하는 포지션을 5개씩 가지고 있다면 중복되는 경우가 아주 많아서 백트래킹에서 걸러지게된다. 따라서 절대 O(5^11) 시간은 나올 수 없고 그보다 훨씬 적은 시간이 들 것으로 예상했다.

 

백트킹을 수행하면서 현재 선수가 원하는 포지션 중 하나에 들어갈 수 있다면 현재 선수의 스탯을 더하고 다음 선수로 넘어간다.

모든 선수를 포지션에 배치한다면 cnt==11이 될 텐데 이때 가장 큰 점수만 저장하도록 하면 답을 구할 수 있다.

 

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
#define fasti ios_base::sync_with_stdio(false); cin.tie(0);
#define fastio ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define INF 1e9+7
#define pii pair<int, int>
 
typedef long long ll;
// typedef pair<int, int> pii;
 
using namespace std;
 
int ans;
// {능력, 포지션}
vector<pii > player[11];
bool visited[11];
 
void input(){
    for(int i = 0; i < 11; i++){
        player[i].clear();
        visited[i] = false;
    }
    ans = 0;
    
    int a;
    for(int i = 0; i < 11; i++){
        for(int j = 0; j < 11; j++){
            cin >> a;
            if(!a) continue;
            player[i].push_back({a, j});
        }
    }
}
 
void dfs(int cnt, int sum){
    if(cnt == 11){
        ans = max(ans, sum);
        
        return;
    }
    
    for(int i = 0; i < player[cnt].size(); i++){
        int score = player[cnt][i].first;
        int position = player[cnt][i].second;
        
        if(visited[position]) continue;
        
        visited[position] = true;
        
        dfs(cnt+1, sum + score);
        
        visited[position] = false;
        
    }
}
 
void solve(){
    dfs(0, 0);
    
    cout << ans << "\n";
}
 
int main(){
    int T;
    cin >> T;
    while(T--){
        input();
        solve();
    }
    
    return 0;
}