swea1865. 동철이의 일 분배

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5LuHfqDz8DFAXc 

SW Expert Academy

def DFS(per,level):
    global Max,N
    if Max>= per: #시간초과 나서 백트래킹
        return

    if level == N:
        if Max<per:
            Max=per
        return

    for i in range(N):
        if not visit[i]: #아직 방문 안했을 때
            visit[i] = 1
            DFS(per*(arr[level][i]/100),level+1)
            visit[i] = 0

T = int(input())
for tc in range(1,T+1):
    N = int(input())
    arr = [list(map(int,input().split())) for _ in range(N)]
    visit = [0]*N
    Max = 0
    DFS(1,0) # percentage,level
    print(f'#{tc} {Max*100:.6f}') #소숫점 6자리까지..