[SWEA/Python] 5209. 최소 생산 비용

📌 문제

https://swexpertacademy.com/main/main.do

SW Expert Academy

 

📌 문제 접근 방법

1. 순열이 필요할 것 같아서 itrertools에서 permutations를 import했더니 시간초과!
2. 재귀를 사용해서 순열을 직접 구현해줬더니 통과했다.
3. 비용을 더한 값이 이미 최소 값보다 커졌다면 return을 해줘서 가지치기를 해줬다.

 

📌 코드

import sys
sys.stdin = open('input.txt')

def permutation(total):
    global factory, min_cost

    if total > min_cost:
        return

    if len(factory) == N:
        min_cost = min(min_cost, total)
        return
    else:
        for i in range(N):
            if i not in factory:
                factory.append(i)
                permutation(total + cost[len(factory)-1][factory[-1]])
                factory.pop()

T = int(input())

for t in range(1, T+1):
    N = int(input())
    cost = [list(map(int, input().split())) for _ in range(N)]
    factory = []

    min_cost = float('inf')
    permutation(0)
    
    print('#{} {}'.format(t, min_cost))