[SWEA] 5189_전자카트

📕 문제

https://swexpertacademy.com/main/learn/course/lectureProblemViewer.do

SW Expert Academy

 

💡 풀이법

1. 앞과 뒤는 무조건 1이어야 하기 때문에 중간에 일의 순서가 될수 있는 경우의 수를 모두 구한다. (완전탐색)

2. 경우의 수를 하나씩 돌면서 그때마다의 배터리 소비량의 총합을 구해서 소비량의 최소합(ans)와 비교한다.

 

from itertools import permutations

T = int(input())
for tc in range(1, T+1):
    N = int(input())
    matrix = [list(map(int, input().split())) for _ in range(N)]
    room_list = [i for i in range(2, N+1)]
    ans = 9999999999
    for item in permutations(room_list, N-1):
        start = 1
        total = 0
        for end in item:
            total += matrix[start-1][end-1]
            start = end
        total += matrix[start-1][0]
        ans = min(ans, total)
    print('#{} {}'.format(tc, ans))