4881. [파이썬 S/W 문제해결 기본] 5일차 - 배열 최소 합_python

문제의 저작권은 SW Expert Academy에 있습니다.

sw expert academy 배열 최소 합

def sol(N, k, s):
    global res
    if N == k :
        if res > s:
            res = s
 
    if res < s:
        return
 
    else:
        for i in range(N):
            if visited[i] == 0:
                visited[i] =1
                sol(N, k+1, s+ data[k][i])
                visited[i] =0
 
TC = int(input())
for tc in range(1, TC+1):
    N = int(input())
    data = [list(map(int, input().split())) for _ in range(N)]
    visited = [0]*N
 
    k = 0
    res = 10*N
 
    sol(N, 0, 0)
    print("#%d %d"%(tc, res))

if res < s:

        return

이 가지치기 부분 안하면 시간 초과 난다.

 

재귀 부분을 간단히 설명하면 k가 행을 나타내고 for문의 i가 열을 나타낸다.