[BOJ 3980] 선발 명단

선수들의 적합한 포지현 수는 최대 5이므로 브루트포스 완전탐색을 하면 시간복잡도가 $O(T*5^{11})=O(T *48,828,125)$이다

전형적인 백트래킹 문제였는데 처음에 내가 짠 함수의 인덱스가 헷갈려서 꼬였다

dfs(table, picked, stats, player_id)에서
table[i][j]: i번째 선수가 j번째 포지션에서의 능력치
picked[j]: j번째 포지션을 선택했는지 True/False 여부
stats[i]: 현재 상태에서의 i번째 선수의 능력치
player_id: 선수 순서, table의 row와 같다

import sys
#sys.stdin = open('input.txt', 'r')
#sys.setrecursionlimit(10**6)
input = sys.stdin.readline

answer = 0
def dfs(table, picked, stats, player_id):
    if player_id == 11:
        global answer
        answer = max(answer, sum(stats))
        return
    
    # 모든 포지션 탐색
    for i in range(11):
    	# i번째 포지션을 선택하지 않았고, 해당 포지션에서의 능력치가 0이 아닐때
        if not picked[i] and table[player_id][i] > 0:
            picked[i] = True
            stats[player_id] = table[player_id][i]
            dfs(table, picked, stats, player_id + 1)
            stats[player_id] = 0
            picked[i] = False

T = int(input())
for _ in range(T):
    table = []
    picked = [False] * 11
    stats = [0] * 11
    answer = 0
    for _ in range(11):
        table.append([int(x) for x in input().split()])
    dfs(table, picked, stats, 0)
    print(answer)