[모든 경우의수 검사]배열최소합 구하기

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45

def backtrack(a, k, input, arr, result): global MAXCANDIDATES global min_value t = 0 c = [0] * MAXCANDIDATES if k == input: # write your code for i in range(1, k+1): t += arr[i-1][a[i]-1] if t > min_value: break elif t <= min_value and i == k: min_value = t result.append(min_value) else: k+=1 ncandidates = construct_candidates(a,k,input,c) for i in range(ncandidates): a[k] = c[i] backtrack(a, k, input, arr, result) #후보군 구하는 함수 def construct_candidates(a, k, input, c): in_perm = [False] * NMAX for i in range(1,k): in_perm[a[i]] = True ncandidates = 0 for i in range(1, input+1): if in_perm[i] == False: c[ncandidates] = i ncandidates += 1 return ncandidates #Main MAXCANDIDATES = 100 NMAX = 100 a = [0] * NMAX for t in range(int(input())): min_value = 999 result = list() n = int(input()) arr = [list(map(int, input().split())) for _ in range(n)] backtrack(a, 0, n, arr, result) print("#{} {}".format(t+1, result))