문제

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

풀이

겹치는 포지션이 없이 모든 포지션을 채우는 최대 능력치의 합을 구하는 문제이다. n이 별로 크지않아서 백트래킹으로 풀었다.

CODE

import sys
from collections import deque

input = sys.stdin.readline
ans = 0
for i in range(int(input())):
    arr = [list(map(int, input().split())) for _ in range(11)]
    chk = [0] * 11
    ans = 0

    def b_trc(player, sco):
        global ans
        if player >= 11:
           ans = max(ans, sco)
           return

        for i in range(11):
            val = arr[player][i]
            if val == 0 or chk[i]:
                continue
            else:
                chk[i] = 1
                b_trc(player + 1, sco + val)
                chk[i] = 0


    b_trc(0, 0)
    print(ans)