# 링크
https://swexpertacademy.com/main/learn/course/subjectDetail.do?courseId=AVuPDYSqAAbw5UW6&subjectId=AWUYEGw61n8DFAVT&&
# 접근
- 모든 화물차들이 편도로 한번만 이동합니다
- 한 번의 이동에 가장 많은 무게를 실어나르는 경우를 찾습니다
- 가장 용량이 큰 화물차에, 그 화물차가 실을 수 있는 가장 무거운 화물을 싣습니다
# 코드
import sys
sys.stdin = open('input.txt')
T = int(input())
for t in range(1, T+1):
N, M = map(int, input().split()) # 컨테이너 수, 트럭 수
containers = list(map(int, input().split())) # 화물들
trucks = list(map(int, input().split())) # 트럭들
# 가장 용량이 큰 트럭부터 가장 큰 화물을 싣는다
# 하나의 화물을 나눠 싣는 경우는 없다
# 모든 트럭의 용량이 가장 작은 화물보다 작으면 결과는 0
containers.sort(reverse=True)
trucks.sort(reverse=True)
# 내림차순 정렬하여 실을 수 있는 큰 화물부터 싣는다
result = 0 # 한 번의 운행에 총 실을 수 있는 화물 무게
i = 0 # i번째 화물
j = 0 # j번째 트럭
# 컨테이너를 가리키는 포인터 i를 통해 화물을 하나씩 트럭으로 싣는다
print(containers)
print(trucks)
while i < len(containers) and j < len(trucks): # 화물과 트럭이 남아있을 때
# 다른 말로 화물을 다 실었거나, 트럭이 전부 차있으면 while문 종료
if trucks[j] >= containers[i]: # 화물을 트럭에 실을 수 있으면
result += containers[i] # 컨테이너를 트럭에 실었다!
i += 1 # 다음 화물~
j += 1 # 다음 트럭~
else: # trucks[i] < containers[i]
# j트럭으로는 i화물을 실을 수 없다
# 하지만 j트럭으로 (i+1)화물은 실을 수 있을지도 모른다
i += 1 # j는 건드리지 않고, 화물만 다음 화물로
# while문 종료: 실을 수 있는 화물들을 전부 실었다
print('#{} {}'.format(t, result))
# 정리
- 주어지는 경우에서 가장 최적의 해, 최고 효율을 내는 경우를 찾는 그리디 문제입니다
- 경험상 그리디 문제는 접근보다 구현과정이 더 복잡한 경우가 많았습니다
- 이 문제도 화물과 트럭 각각 for문을 사용하여 이중for문으로 푸는 코드도 있었지만
- 운 좋게 위와같은 방법을 떠올려 비교적 간단히 해결할 수 있었던 것 같습니다
- 무게순으로 정렬된 화물과 트럭을 각각 가리키며
- "이 화물을 이 트럭이 실을 수 있는가"만 확인하고
- 실을 수 있으면 싣고, 싣지 못한다면 남은 뒤의 트럭도 그 화물을 실을 수 없습니다
- 때문에 화물을 가리키는 포인터만 하나 뒤로 옮겨줍니다
사실 무거운 화물을 실은 트럭과 비교적 가벼운 화물을 실은 트럭이 동일한 속도로 이동한다는 자체가 매우 큰 비용적 손해이긴 하지만
댓글