[SWEA] 4881. 배열 최소 합 - Python

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

SW Expert Academy

< 📝 문제 >

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

 

에서 두 개 이상의 숫자를 고를 수 없다.

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

 

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

2	1	2
5	8	5
7	2	2

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

< ❓ 생각 >

< 💻 코드 >

def min_v(idx, sum_v):
    global min_sum
    # 최솟값보다 크면 필요없음
    if sum_v >= min_sum:
        return
    # 모든 고름
    if idx == N:
        if min_sum > sum_v:
            min_sum = sum_v
            return
    # 각 열에서 고르기
    for i in range(N):
        if not col_used[i]:
            col_used[i] = 1
            min_v(idx + 1, sum_v + arr[idx][i])
            # 복구
            col_used[i] = 0

# 테스트 케이스 개수
T = int(input())
for tc in range(1, 1 + T):
    # N*N 배열
    N = int(input())
    arr = [list(map(int,input().split())) for _ in range(N)]
    # 열을 사용했는가
    col_used = [0] * N
    min_sum = 100000
    min_v(0, 0)
    print(f'#{tc} {min_sum}')

< ❗ 느낀 점 >

행도 고려하느라 조금 어려웠다..ㅜ