Problem

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

Solving

아이디어

컨테이너와 트럭 리스트를 각각 내림차순으로 정렬 (옮기는 화물들의 총 중량이 최대인 경우를 알아야하기 때문에 큰 값부터 옮길 수 있는지 조사하기 위해 내림차순으로 정렬한다. 매 트럭마다 가장 무거운 화물을 옮기면 결국 최대 중량을 알 수 있다.)
이중 for문 (트럭기준으로 반복문을 돌면서, 각 트럭마다 화물 리스트를 반복문을 통해 탐색한다.)
이미 옮긴 화물은 체크표시한다. (중첩 계산 방지)
옮기는 화물의 무게를 더해준다.

코드

for tc in range(1, int(input()) + 1):
    N, M = map(int, input().split())
    containers = list(map(int, input().split()))
    trucks = list(map(int, input().split()))

    containers.sort(reverse=True)
    trucks.sort(reverse=True)

    sum_v = 0   # 옮겨진 화물의 무게 더하기
    checked = [0] * N   # 옮겨진 화물 체크
    # 가장 적재용량이 큰 트럭부터 조사
    for i in range(M):
        # 트럭 리스트의 인덱스가 화물의 총량을 넘어간 경우 = 트럭이 남는 경우 = 모든 화물을 옮긴 경우
        # 종료
        if i == N:
            break
        # 아직 남아있는 화물 조사해서 체크
        for j in range(i, N):
            # 이미 옮긴 화물은 건너뛰기
            if checked[j]: continue
            # 트럭의 적재용량이 화물의 무게보다 클 때만 옮긴다.
            if trucks[i] >= containers[j]:
                checked[j] = 1  # 화물을 옮겼다고 체크
                sum_v += containers[j]  # 무게 더해주기
                break   # 이번 트럭은 끝났으니 다음 트럭 조사하기 위해 break
    
    # print(checked)
    # print(containers)
    # print(trucks)
    print(f'#{tc} {sum_v}')

저작자표시