5209 최소 생산 비용

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

※ SW Expert Academy 에디션의 무단복제를 금합니다.

A 회사는 여러 공장을 가지고 있습니다. 봄부터 N공장에서 N종의 신제품을 순차적으로 생산할 예정이다.

공장별 각 제품의 생산 원가를 고려하여 모든 제품의 최소 생산 원가를 계산하는 프로그램을 작성하십시오.

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

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

(기입)

테스트 케이스의 수 T는 첫 번째 줄에 지정됩니다. 1<=티<=50

다음 라인부터 제품 수 N과 공장당 생산 비용 V가 N 라인에 걸쳐 각 테스트 케이스에 대한 첫 번째 라인에 제공되고 제품당 한 라인에 제공됩니다.ij주어진 3<=N<=15, 1<=Vij<=99

(누르다)

각 줄에 “#T”(T는 테스트 케이스 번호)를 인쇄한 후 응답을 인쇄합니다.

(내 솔루션)

def per(k, curS):          # 함수에 넣어주는 값으로 시작 값, 합
    global minV
    if curS > minV:        # 합이 최소값 넘어가버리면 종료
        return
    if k == N:             # N 길이의 조합 만들었을 시
        if minV > curS:    # 합과 최소값 비교
            minV = curS
        return


    for i in range(N):              # 한 줄에 하나씩만 골라야 하므로
        if not visited(i):          # 방문하지 않았을 시
            visited(i) = True       # 방문표시
            bits(i) = arr(k)(i)     # 비트의 i번째 자리를 줄에 하나씩 고른 값으로 넣어줌
            per(k+1, curS + arr(k)(i))    # k+1번째 자리에 넣어줄 다음 함수 실행, 합에 이미 넣은 값 추가
            visited(i) = False



T = int(input())

for tc in range(1, T+1):
    N = int(input())
    arr = (list(map(int, input().split())) for _ in range(N))
    bits = (-1) * N
    visited = (False) * N
    minV = 1500000
    per(0, 0)
    print(f'#{tc} {minV}')