[Python3] SWEA 컨테이너 운반 5201

문제 :

화물이 실려 있는 N개의 컨테이너를 M대의 트럭으로 A도시에서 B도시로 운반하려고 한다.
트럭당 한 개의 컨테이너를 운반 할 수 있고, 트럭의 적재용량을 초과하는 컨테이너는 운반할 수 없다.
컨테이너마다 실린 화물의 무게와 트럭마다의 적재용량이 주어지고, A도시에서 B도시로 최대 M대의 트럭이 편도로 한번 만 운행한다고 한다.
이때 이동한 화물의 총 중량이 최대가 되도록 컨테이너를 옮겼다면, 옮겨진 화물의 전체 무게가 얼마인지 출력하는 프로그램을 만드시오.

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

 

접근 :

그리디 문제이므로, 정렬을 활용해 문제를 풀 수 있다는 접근은 쉽다.

가장 적재용량이 높은 트럭이 가장 무거운 짐을 운반할 수 없다면, 그 컨테이너는 주어진 어떤 트럭도 운반할 수 없다.

그렇기 때문에 pop을 통해 그 컨테이너를 버리면 된다.

짐 운반이 되면 운반된 트럭을 누적합으로 더하고, pop으로 버린다.

트럭 배열이 한 바퀴 다 돌면 문제가 끝난다.

 

풀이 :

T = int(input())

for tc in range(1, T+1):
    N, M = map(int, input().split())
    container = sorted(list(map(int, input().split())), reverse=True)
    truck = sorted(list(map(int, input().split())), reverse=True)
    ans = 0
    for i in range(len(truck)):
        while container :
            if truck[i] >= container[0] :
                ans += container[0]
                container.pop(0)
                break
            else:
                container.pop(0)
    print(f'#{tc} {ans}')