최소생산비용 Python(SW Expert Academy, SWEA)

난이도 : D3

문제번호 : 5209

※ 저의 풀이가 무조건적인 정답은 아닙니다.

다른 코드가 좀더 효율적이고 좋을 수 있습니다.

다른사람들의 풀이는 언제나 참고만 하시기 바랍니다.

문제 주소 및 출처입니다.

https://swexpertacademy.com/main/learn/course/subjectDetail.do?courseId=AVuPDYSqAAbw5UW6&subjectId=AWUYGf7K180DFAVT#

SW Expert Academy

---

목차

1. 문제 설명

2. 문제 해석

3. 소스 코드

---

1. 문제 설명

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

예시

입력	출력
3 3 73 21 21 11 59 40 24 31 83 5 93 4 65 31 66 63 12 60 60 84 87 57 44 35 20 12 9 40 12 40 60 21 3 49 54 6 55 83 32 79 53 70 77 88 80 93 42 29 54 26 5 10 25 94 77 92 82 83 11 51 84 11 21 62 45 58 37 88 13 34 41 4	#1 63 #2 78 #3 129

---

2. 문제풀이

전기버스 2와 같은 유형이다. 다른점이 있다면 가지치기 하는 조건이 최소 비용으로 바뀌었을 뿐이다. 한 공장당 하나만 생산하려 하기때문에 기준을 공장으로 잡고 생산비용을 이동하며 재귀를 한다. 백트래킹에 걸리는 부분은 뒤에를 보지 않아도 최소비용보다 크므로 배제하게 된다. 마지막까지 갔을때 백트래킹에 걸리지 않았다면 그것이 최소비용이므로 갱신을 한다.

---

3. 소스코드

 

#D3 5209 최소 생산비용
 
def dfs(idx, _sum):
    global answer
    if _sum >= answer:
        return
    if idx == N:
        answer = _sum
    for i in range(N):
        if visited[i]:
            visited[i] = 0
            dfs(idx+1, _sum + V[idx][i])
            visited[i] = 1
 
 
for t in range(int(input())):
    N = int(input())
    V = [list(map(int, input().split())) for _ in range(N)]
    visited = [1 for _ in range(N)]
    answer = 999999
    dfs(0, 0)
    print('#{} {}'.format(t+1, answer))