[파이썬 | SW Expert Academy] 최소 생산 비용

[입력]

A사는 여러 곳에 공장을 갖고 있다. 봄부터 새로 생산되는 N종의 제품을 N곳의 공장에서 한 곳당 한가지씩 생산하려고 한다.

각 제품의 공장별 생산비용이 주어질 때 전체 제품의 최소 생산 비용을 계산하는 프로그램을 만드시오.

예를 들어 3개의 제품을 생산하려는 경우 각 공장별 생산비용은 다음과 같이 주어진다..

	A	B	C	공장
1	73	21	21
2	11	59	40
3	24	31	83
제품

이때 1-C, 2-A, 3-B로 제품별 생산 공장을 정하면 생산 비용이 21+11+31=63으로 최소가 된다.


[입력]

첫 줄에 테스트케이스의 수 T가 주어진다. 1<=T<=50

다음 줄부터 테스트 케이스의 별로 첫 줄에 제품 수 N이 주어지고, 이후 제품당 한 줄 씩 N개의 줄에 걸쳐 공장별 생산비용 Vij가 주어진다. 3<=N<=15,   1<=Vij<=99
 
[출력]

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

 

[풀이] 

 

제품별로 점점 재귀적으로 탐색을 해나가면서, 해당 제품에 고른 회사를 banList 배열에 체크해서 백트래킹을 한다.

마찬가지로 최소비용을 구하는 문제이므로 비용이 지금까지의 최소비용보다 올라가면 바로 return해서 시간 이득을 볼 수 있다.

 

 

# SWEA 최소생산비용
def bt(idx, val):
    global minans
 
    if val > minans:
        return
 
    if idx == N-1:
        if minans > val:
            minans = val
        print(minans)
        return
    
    for i in range(N):
        if banList[i] == 0:
            banList[i] = 1
            bt(idx+1, val+V[idx+1][i])
            banList[i] = 0
 
T = int(input())
 
for t in range(1, T+1):
    minans = 999999
    
    N = int(input())
 
    banList = [0]*N
    V = []
    for _ in range(N):
        V.append(list(map(int, input().split())))
    
    for i in range(N):
        banList[i] = 1
        bt(0, V[0][i])
        banList[i] = 0
    
    print("#%d %d" % (t, minans))