[SWEA] 5201 컨테이너 운반 - GREEDY

이 글은 SW Expert Academy에 있는 문제를 풀고 정리한 글입니다.

https://swexpertacademy.com/main/learn/course/lectureProblemViewer.do

이 문제를 완전 탐색으로 푼다면

각 트럭에 대해서 실을 수 있는 화물을 번갈아 가면서 실어보는 식으로 탐색 해볼 수 있겠죠.

하지만 지수적으로 경우의 수가 증가할 수 있고, n,m<=100 이기 때문에 이 방법은 시간 안에 작동하지 않을 수 있습니다.

그리고... 이 문제가 탐욕법 학습을 위해 준비된 문제니까

일단 탐욕법으로 접근 해보겠습니다.

이 문제의 핵심은 결국 무거운 화물들을 최대한으로 실으면 되는겁니다.

그래서 선택 알고리즘을 설계할 때 무거운 화물들부터 트럭으로 실을 수 있는지 검사하기로 했습니다.

그렇다면 화물들을 내림차순으로 정렬해서 순서대로 검사할 때, 꼭 남은 화물들 중에서 가장 무거운 화물을 싣는게

최적해로 가는 선택인지를 알아야 합니다.

만약에 중간에 실을 수 있는 가장 무거운 화물을 싣지 않고 그보다 가벼운 화물을 실어서 얻은 최적해가 있다고 가정하면,

나머지 화물들은 그대로 두고, 그 가벼운 화물 대신 그 당시에 남은 가장 무거운 화물을 실어서 얻을 수 있는 최적해도

분명 존재하므로, 위에 세운 알고리즘이 최적해에 가는 선택임을 알 수 있습니다.

http://colorscripter.com/s/pyAafxy