[SW Expert Academy] 5209. 최소 생산 비용

5209. 최소 생산 비용

---

문제)

 

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

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

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

 

 

이때 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는 테스트 케이스 번호)를 출력한 뒤, 답을 출력한다.

 

 

 

 

 

 

풀이)

 

일반적인 백트래킹 + 가지치기를 이용하여 풀었다.

 

def recur(cur, total):
    global ans, pruning
    
    # 처음 계산이 끝나고 난 뒤, 그 값을 이용하여 가지치기
    if total > pruning:
        return
 
    # 최소 생산 비용 갱신
    if cur == n:
        ans = min(ans, total)
        pruning = total
        return
    
    # 모든 방법으로 제품을 만들기
    for i in range(n):
        if visited[i]:
            continue
        visited[i] = 1
        recur(cur + 1, total + li[cur][i])
        visited[i] = 0
 
 
T = int(input())
for _ in range(T):
    n = int(input())
    li = [list(map(int, input().split())) for i in range(n)]
    ans = pruning = 1 << 20
    visited = [0] * n
    recur(0, 0)
    print(f"#{_ + 1} {ans}")

 

---

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

SW Expert Academy

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

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