중복없는 순열 문제이다. 여기서는 값을 곱해가면서 구하는데, 곱할수록 값이 작아지는 걸 활용해 가지치기 한다.
곱할수록 값이 작아지니, 현재 구한 최대 확률보다 지금 구하고 있는 확률이 더 작으면 종료하고 다음 재귀를 탐색한다.
def recur(cur, percent):
global mmax
if percent <= mmax:
return
if cur == n:
mmax = max(mmax, percent)
return
for i in range(n):
if visited[i]:
continue
visited[i] = 1
recur(cur + 1, percent * (arr[cur][i] / 100))
visited[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)]
visited = [0 for _ in range(n)]
mmax = 0
recur(0, 1)
print(f'#{tc} {mmax * 100:.6f}')