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

문제

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

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

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

2	1	2
5	8	5
7	2	2

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

 

[입력]
 

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

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

 

[출력]
 

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

 

 

★ 시작하기 전에

조합문제라고 생각했다. 결국 행,열이 같기 때문에 하나의 행지나가면서 열 Index를 지정해 주면된다.

즉! sel 리스트에 겹치지 않고 n개의 항목을 넣어주는 조합이 되는 것이다.

조합을 구성하는 방법은 여러가지이지만 보편적인 재귀 형식 + check 리스트를 활용하여 구현하였다.

 

T = int(input())

# 조합 문제! 조합 형식은 외우듯이 표현할 줄 알아야한다!
def perm(idx, total):
    global mini
    if idx == n:
        total = sum(sel)
        if total < mini:
            mini = total
    # 이거 없으면 틀린다... 가지치기... 가지치기... 생각하자 무조건
    # 결국 앞서 TOTAL값보다 크면 더이상 진행할 필요가 없다.
    if total > mini:
        return
    
    # 조합을 위해 한자리씩 채우고 들어간 후, 나올때 다시 CHECK를 0으로 바꾸어야한다!
    for j in range(n):
        if check[j]:continue
        check[j] = 1
        sel[idx] = board[idx][j]
        perm(idx + 1, total + sel[idx])
        check[j] = 0

for tc in range(1,T+1):
    n = int(input())
    board = [list(map(int,input().split())) for _ in range(n)]
    check = [0 for _ in range(n)]
    sel = [0 for _ in range(n)]
    mini = 100000
    perm(0, 0)
    print('#{} {}'.format(tc, mini))

여기서 가장 중요한 것이 가지치기 이다. 가지치기가 없으면 pass가 되지 않는다.

가지치기를 생각하는건 어렵다. 익숙하지 않아서일까?

완전탐색만 하다보니까 그냥 나머지 경우는 걸러지겟지라는 생각을 하는데 이 경우 메모리 차이 및  실행 시간이 차이가 많이난다.

 

현재 풀이를 하면 어떻게 하면 되지 않을까? 라는 생각이 되면서 시도하는 정도까지 온 것 같다.

하지만 메모리 문제, 실행 시간에 대한 생각을 하지 못하며 최적 접근법에 대한 훈련이 필요한 것 같다!