[알고리즘] 순열과 SWEA 최소 생산 비용

기본 순열 코드

jam = ['A','B','C']
pos = ['','','']
check = [0,0,0]
def perm(depth):
    if depth == 3:
        print(*pos)
        return
    for i in range(3): # 0 1 2
        if not check[i]:
            check[i] = 1
            pos[depth] = jam[i] # jam[i] = A B C
            perm(depth+1)
            check[i] = 0

perm(0)

최종 출력:

A B C
A C B
B A C
B C A
C A B
C B A

SWEA 최소 생산 비용

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

SW Expert Academy

 

위 문제를 요약하면 다음과 같다.

공장과 공장에서 생산 가능한 제품이 있다.

공장별로 각 제품을 생산할 때의 비용이 다르다.

공장들은 서로 다른 제품을 생산해야 한다.

공장들이 서로 다른 제품을 생산해낼 때의 비용을 모두 합해서 최소 비용이 나오는 경우의 비용을 출력해야하는 문제이다.

 

소요시간 : 약 20분

처음 코드(테스트케이스 10개 중 6개 정답)

T = int(input())

def perm(depth, cost):
    global pos, check, N, costs
    if depth == N:
        costs.append(cost)
        return
    for i in range(N):
        if not check[i]:
            check[i] = 1
            cost += int(pos[depth][i])
            perm(depth+1, cost)
            check[i] = 0
            cost -= pos[depth][i]

for i in range(T):
    N = int(input())
    pos = []
    costs = []
    check = [0] * N
    for j in range(N):
        pos.append(list(map(int, input().split())))
    perm(0, 0)
    print(f"#{i+1} {min(costs)}")

 

최종 코드

‘중간 단계에서 이미 다른 최종 비용보다 값이 커진다면 해당 경우의 수는 더 이상 검토할 필요가 없다.’

cost가 넘어갈 때는 재귀를 돌리지 않음으로써 시간 초과를 해결하였다.

T = int(input())

def perm(depth, cost):
    global pos, check, N, costs
    if depth == N:
        costs.append(cost)
        return
    for i in range(N):
        if not check[i]:
            check[i] = 1
            cost += int(pos[depth][i])
            if costs and min(costs) < cost:
                check[i] = 0
                cost -= pos[depth][i]
            else:
                perm(depth+1, cost)
                check[i] = 0
                cost -= pos[depth][i]

for i in range(T):
    N = int(input())
    pos = []
    costs = []
    check = [0] * N
    for j in range(N):
        pos.append(list(map(int, input().split())))
    perm(0, 0)
    print(f"#{i+1} {min(costs)}")