Algorithm

SWEA 5209 최소 생산 비용 (python)

광보기 2021. 4. 21. 16:34
반응형

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

 

[파이썬 S/W 문제해결 구현] 5일차

2021.04.21 - [Algorithm] - SWEA 5208 전기버스2 (python)

2021.04.21 - [Algorithm] - SWEA 5209 최소 생산 비용 (python)

 

문제

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

[입력]

첫 줄에 테스트케이스의 수 T가 주어진다. 1<=T<=50

다음 줄부터 테스트 케이스의 별로 첫 줄에 제품 수 N이 주어지고, 이후 제품당 한 줄 씩 N개의 줄에 걸쳐 공장별 생산비용 Vij가 주어진다. 3<=N<=15, 1<=Vij<=99

[출력]

각 줄마다 "#T" (T는 테스트 케이스 번호)를 출력한 뒤, 답을 출력한다.

풀이과정

  • 이전에 비슷한 문제를 풀었던 적이 있다. 그것보단 조금 쉬웠다. 링크참고
    • y,x 인덱스가 하나도 겹치지 않게 골고루 들어가라는 조건이었다.
    • 이를 위해 y를 idx 로 정하고
    • x는 반복문을 통해서 해결했다.

코드

T = int(input())

# 비용 계산 함수
# 인덱스와 합을 받을 예정
# idx 값은 y값이라고 생각하면 된다.
def cost(idx, total):
    global result
    # 시간초과와 계산 번거로움줄이기 위한 코드
    # 만약 값이 이미 구한 값 초과한다면 종료
    if total >= result:
        return
    # 만약 다 검사를 마쳤다면
    if idx == N:
        # total 값은 결과값 ( 위에서 이미 걸렀기 때문 )
        result = total
        return
    # N만큼 돌면서 x축검사
    for i in range(N):
        # 만약 x의 인덱스가 방문한 적이 없다면
        if not visited[i]:
            # 방문 후 다음 idx값 살펴보고 다시 돌아오는 과정
            visited[i] = 1
            cost(idx+1, total+arr[idx][i])
            visited[i] = 0


for tc in range(1, T+1):
    N = int(input())
    arr = [list(map(int, input().split())) for _ in range(N)]
    visited = [0 for _ in range(N)]
    result = 100 * N
    cost(0, 0)

    print("#{} {}".format(tc, result))
반응형