컨테이너 운반 Python(SW Expert Academy, SWEA)

난이도 : D3

문제번호 : 5021

※ 저의 풀이가 무조건적인 정답은 아닙니다.

다른 코드가 좀더 효율적이고 좋을 수 있습니다.

다른사람들의 풀이는 언제나 참고만 하시기 바랍니다.

문제 주소 및 출처입니다.

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

SW Expert Academy

---

목차

1. 문제 설명

2. 문제 해석

3. 소스 코드

---

1. 문제 설명

화물이 실려 있는 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는 테스트 케이스 번호)를 출력한 뒤, 답을 출력한다.

예시

입력	출력
3 3 2 1 5 3 8 3 5 10 2 12 13 11 18 17 4 7 20 3 9 7 9 20 5 10 12 10 13 14 6 19 11 5 20 11 14 5 18 17 8 9 17 18 4 1 16 15 13	#1 8 #2 45 #3 84

---

2. 문제풀이

트럭당 여러개의 컨테이너를 옮길 수 있다면 어려워 졌을 문제였지만 트럭당 1개만 가능하다고 한다. 와우! 정렬하면 되겠네 트럭과 컨테이너를 오름차 정렬한다음에 뒤에서 부터 꺼낸다(그래야 O(1)) 트럭과 컨테이너를 비교하여 트럭이 컨테이너를 감당할 수 있다면 answer에 무게를 추가하고 안쪽 반복문을 멈춘다. 모든 트럭 혹은 컨테이너가 떨어질때까지 반복한다. 꺼내진 트럭이 감당못하는 컨테이너라면 정렬했기 때문에 다른 트럭들도 감당하지 못할것이다.

---

3. 소스코드

 

#5021 D3 컨테이너 운반
 
for t in range(int(input())):
    answer = 0
    N, M = map(int, input().split())
    N_list = sorted(list(map(int, input().split())))
    M_list = sorted(list(map(int, input().split())))
    #트럭과 컨테이너가 남아있을때까지 반복
    while M_list and N_list:
        truck = M_list.pop()
        #컨테이너가 남아있을때까지 반복
        while N_list:
            container = N_list.pop()
            #트럭이 화물을 실을 수 있다면
            if truck >= container:
                #정답에 무게 추가
                answer += container
                break
    print('#{} {}'.format(t+1, answer))