[백준] 3980 - 선발 명단

간만에 원큐에 푼 문제라 기분이 너무 좋다...

그냥 재귀로 싹다 돌려줘도 되는 문제

물론 전체 포지션을 다 고려한다고 했을 경우에는 O(11^11)이라 밥먹고 오면 풀릴 시간이지만

문제 조건이 '한명당 적합한 포지션은 최대 5개'라는 조건이 붙어 있어서 O(5^11) 까지 줄어드는 문제

#include <iostream>
#define SIZE 13
using namespace std;
 
int S[SIZE][SIZE];
bool check[SIZE];
int C, dab;
 
void dfs(int d, int sum)
{
    if (d == 11)
    {
        dab = dab > sum ? dab : sum;
        return;
    }
    for (int i = 0; i < 11; i++)
    {
        if (check[i] || !S[d][i]) continue;
        check[i] = true;
        dfs(d + 1, sum + S[d][i]);
        check[i] = false;
    }
}
 
int main(void)
{
    cin >> C;
    while (C--)
    {
        dab = 0;
        for (int i = 0; i < 11; i++)
        {
            check[i] = false;
            for (int j = 0; j < 11; j++)
                cin >> S[i][j];
        }
        dfs(0, 0);
        cout << dab << "\n";
    }
    return 0;
}