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

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

 

 

이 문제는 11명의 선수가 주어지고 선수당 각자의 포지션에 대한 능력치가 존재할때 그 합이 최대인 것을 구하는 문제이다.

 

선수는 최대 11명 고정으로 11명을 일렬로 나열하는 경우가 최악이 되지만 이때 능력치가 0인 경우는 무시하면 이것보다 훨씬 더 적게 나오기 때문에 모든 경우를 찾아보며 최댓값을 갱신해주면 된다.

 

N의 크기를 보면 쉽게 알고리즘을 생각할 수 있는 문제였다.

 

 

정답코드

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
#define endl "\n"
#define MAX 1e9

struct coordinate {
    int x;
    int y;
    int r;
};

int dx[] = {-1, 1, 0, 0, 1, -1, -1, 1};
int dy[] = {0, 0, -1, 1, -1, 1, -1, 1};
int T, answer;
bool visited[11];

void bt(int x, int cnt, vector<vector<int>> &graph, int val) {
    if(cnt == 11) {
        answer = max(answer, val);
        return;
    }

    for(int i = 0; i < 11; i++) {
        if(graph[x][i] > 0 && !visited[i]) {
            visited[i] = true;
            bt(x+1, cnt+1, graph, val + graph[x][i]);
            visited[i] = false;
        }
    }
}

void solve(vector<vector<int>> &graph) {
    bt(0, 0, graph, 0);

    cout << answer << endl;
}

void input() {
    cin >> T;

    while(T--) {
        answer = 0;
        vector<vector<int>> v(11, vector<int>(11, 0));

        for(auto &it : v) {
            for(auto &iter : it) {
                cin >> iter;
            }
        }

        solve(v);
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    input();
}