SWEA 5201 컨테이너 운반 (python)

 

5201. [파이썬 S/W 문제해결 구현] 3일차 - 컨테이너 운반 D3

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

2021.04.20 - [분류 전체보기] - SWEA 5202 화물도크 (python)

2021.04.20 - [분류 전체보기] - SWEA 5203 베이비진 게임 (python)

문제

화물이 실려 있는 N개의 컨테이너를 M대의 트럭으로 A도시에서 B도시로 운반하려고 한다.

트럭당 한 개의 컨테이너를 운반 할 수 있고, 트럭의 적재용량을 초과하는 컨테이너는 운반할 수 없다.

컨테이너마다 실린 화물의 무게와 트럭마다의 적재용량이 주어지고, A도시에서 B도시로 최대 M대의 트럭이 편도로 한번 만 운행한다고 한다.

이때 이동한 화물의 총 중량이 최대가 되도록 컨테이너를 옮겼다면, 옮겨진 화물의 전체 무게가 얼마인지 출력하는 프로그램을 만드시오.

화물을 싣지 못한 트럭이 있을 수도 있고, 남는 화물이 있을 수도 있다. 컨테이너를 한 개도 옮길 수 없는 경우 0을 출력한다.

[입력]

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

다음 줄부터 테스트 케이스의 별로 첫 줄에 컨테이너 수 N과 트럭 수 M이 주어지고, 다음 줄에 N개의 화물이 무게wi, 그 다음 줄에 M개 트럭의 적재용량 ti가 주어진다.

1<=N, M<=100, 1<=wi, ti<=50

[출력]

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

풀이

T = int(input())

for tc in range(1, T+1):
    N, M = map(int, input().split())
    weight = list(map(int, input().split()))
    capacity = list(map(int, input().split()))

    # 화물은 하나씩만 담을 수 있으므로 가장 큰 화물을 가장 큰 트럭에 담는것이 최고이다.

    # 이를 위해 무게와 용량을 큰순서대로 정렬해준다.
    sorted_weight = sorted(weight, reverse=True)
    sorted_capacity = sorted(capacity, reverse=True)
    # 결과값을 초기화 해준다. (트럭수만큼)
    result = [0 for _ in range(M)]

    # 화물들을 번갈아 가면서 넣어본다.
    for i in range(N):
        # 화물에 맞는 트럭을 검사한다.
        for j in range(M):
            # 만약 화물을 적재할 수 있을때
            if sorted_weight[i] <= sorted_capacity[j]:
                # 그 트럭에 아무것도 실려있지 않다면
                if not result[j]:
                    # 트럭에 적재를 한다.
                    result[j] = (sorted_weight[i])
                    # 그리고 이 짐은 이미 실렸기 때문에 break 하여 다음 짐을 본다.
                    break

    print("#{} {}".format(tc, sum(result)))

• 보완점 및 추가점
  • 조금 더 간단하게 코드를 짤 수 있을것 같았다.
  • 순열로 풀어보며 완전검색을 해보는 것? 도 좋을 것 같다.