백준 3980번 선발 명단 C++

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

3980번: 선발 명단

 

백트래킹, 능력치가 0이면 배치할 수 없다는 것이 핵심

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <list>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <limits.h>

using namespace std;
using int64 = long long;

vector<vector<int>> abilities;
vector<bool> included;
int ans;

void BT(int pos, int sum) {
    if (pos >= 11) {
        ans = max(ans, sum);
        return;
    }
    for (int i = 0; i < 11; i++) {
        if (included[i]) continue;
        int ability = abilities[i][pos];
        if (ability == 0) continue;
        included[i] = true;
        sum += ability;
        BT(pos + 1, sum);
        included[i] = false;
        sum -= ability;
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    abilities = vector<vector<int>>(11, vector<int>(11));
    int t;
    cin >> t;
    while (t--) {
        ans = -1;
        included = vector<bool>(11, false);
        for (int i = 0; i < 11; i++) {
            for (int j = 0; j < 11; j++) {
                cin >> abilities[i][j];
            }
        }
        BT(0, 0);
        cout << ans << "\n";
    }
}