[CodeUp/2841] Minimum Sum (Tiny) (Python)

Problem : https://codeup.kr/problem.php?id=2841&rid=0

Status : Solved

Time : --

 

---

 

문제 설명

 

n*n개의 수가 주어진다. (1<=n<=10)

이때 겹치지 않는 각 열과 각 행에서 수를 하나씩 뽑는다. (즉, 총 n개의 수를 뽑을 것이다, 그리고 각 수는 100이하의 값이다.)

이 n개의 수의 합이 최소가 되게하여라.

 

입력 및 출력

 

입력

첫 줄에 n이 입력된다. 다음 줄 부터 n+1줄 까지 n개씩의 정수가 입력된다.

 

출력

구한 최소 합을 출력한다

 

입력 예시

3

1 2 5

2 4 3

5 4 3 

 

출력 예시

 7

 

 

---

 

풀이

 

이전에 푼 문제와 동일하다. 설명은 이것으로 갈음하겠다.

2022.11.27 - [알고리즘 문제/CodeUp] - [CodeUp/3515] 사탕 줍기 2 (python)

 

n = int(input())
num_list = [list(map(int, input().split())) for _ in range(n)]
visited = [float('inf')]*(1 << n)
q = [(0, 0, 0)]

while q :
  tot_num, visit, idx = q.pop()
  if idx == n :
    continue

  for i in range(n) :
    if visit | (1 << i) != visit :
      new_visit = visit | (1 << i)
      new_tot_num = tot_num + num_list[idx][i] 
      if visited[new_visit] > new_tot_num:
        visited[new_visit] = new_tot_num
        q.append((new_tot_num, new_visit, idx+1))

print(visited[-1])

풀이 완료!