[SW Expert Academy] 4881. 배열 최소 합

4881. 배열 최소 합

---

문제)

 

NxN 배열에 숫자가 들어있다. 한 줄에서 하나씩 N개의 숫자를 골라 합이 최소가 되도록 하려고 한다. 단, 세로로 같은 줄에서 두 개 이상의 숫자를 고를 수 없다.

조건에 맞게 숫자를 골랐을 때의 최소 합을 출력하는 프로그램을 만드시오.

예를 들어 다음과 같이 배열이 주어진다.

 

 

이 경우 1, 5, 2를 고르면 합이 8로 최소가 된다.

 

[입력]
 

첫 줄에 테스트 케이스 개수 T가 주어진다.  1≤T≤50
 

다음 줄부터 테스트 케이스의 첫 줄에 숫자 N이 주어지고, 이후 N개씩 N줄에 걸쳐 10보다 작은 자연수가 주어진다. 3≤N≤10

 

[출력]
 

각 줄마다 "#T" (T는 테스트 케이스 번호)를 출력한 뒤, 합계를 출력한다.

 

 

 

풀이)

def recur(cur):
    global total, result
 
    if total > result: # 가지치기
        return
    
    if cur == n:    # 기저 조건
        if total < result:
            result = total
        return result
 
    for i in range(n):
        if visited[i] == True:
            continue
 
        total += arr[cur][i]
        visited[i] = True
        recur(cur + 1)
        visited[i] = False
        total -= arr[cur][i]
 
T = int(input())
for _ in range(T):
    n = int(input())
    arr = [list(map(int, input().split())) for i in range(n)]
    visited = [False for i in range(n)]
 
    total = 0
    result = 100
    recur(0)
 
    print(f"#{_ + 1} {result}")

---

문제 출처 : https://swexpertacademy.com/main/main.do

SW Expert Academy

※ SW Expert 아카데미는 원칙적으로 문제를 무단 복제하는 것을 금지합니다.

학습용으로 문제를 가져왔으나, 문제가 될 시 수정 및 삭제하겠습니다.