[Python | SWEA] 5209. [파이썬 S/W 문제해결 구현] 5일차 - 최소 생산 비용

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

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으로 최소가 된다.

 

제출 답안

def dfs(n, total):
    global answer

    # 가지치기
    if answer<=total:
        return
    
    # 종료조건
    if n==N:
        if total<answer:
            answer = total
        return
    
    for j in range(N):
        if visited[j] == 0:
            visited[j]=1
            dfs(n+1, total+arr[n][j])
            visited[j]=0


T = int(input())
for test_case in range(1, T+1):
    N = int(input())
    arr = [list(map(int, input().split())) for _ in range(N)]
    answer = 1500
    visited = [0]*N
    dfs(0,0)

    print(f"#{test_case} {answer}")