質問する

入力

しゅつりょく

コード#コード#

# 최소합을 찾는 함수
def find_sum(num):
    # 최종 결과를 저장할 변수와, 숫자들의 합을 임시로 저장할 변수
    global min_sum, sum_num

    # 찾은 최소합보다 임시로 저장한 합이 더 클 경우엔 더 이상 최소값이 아니기 때문에 return
    if min_sum < sum_num:
        return

    # 마지막줄까지 탐색을 끝낸 경우
    if num == N:
        if sum_num < min_sum:   # 두 변수에 저장된 값 중 최소값을 최종 결과를 저장할 변수에 넣어줌
            min_sum = sum_num

    # 세로줄을 돌면서 탐색
    for i in range(N):
        if not visited[i]:      # 방문하지 않았을 경우
            visited[i] = 1      # 방문했다고 표시
            sum_num += num_list[num][i]     # 현재 인덱스 위치의 값울 임시 합 변수에 저장함
            find_sum(num + 1)       # 다음 줄로 넘어가서 확인
            visited[i] = 0          # 확인이 끝나고 방문 표시와 앞서 더해줌 값을 다시 빼줌
            sum_num -= num_list[num][i]


T = int(input())
for tc in range(1, T + 1):
    N = int(input())
    num_list = [list(map(int, input().split())) for _ in range(N)]
    visited = [0] * N       # 방문 표시를 할 리스트
    sum_num = 0             # 임시 합을 저장할 변수
    min_sum = 10 * N        # 최솟값을 저장할 변수
    find_sum(0)             # 함수 호출

    print(f'#{tc} {min_sum}')

解答方法