반응형
탐욕
-
프로그래머스 구명보트 C++프로그래머스(Programmers) 2022. 3. 11. 23:18
제한사항 무인도에 갇힌 사람은 1명 이상 50,000명 이하입니다. 각 사람의 몸무게는 40kg 이상 240kg 이하입니다. 구명보트의 무게 제한은 40kg 이상 240kg 이하입니다. 구명보트의 무게 제한은 항상 사람들의 몸무게 중 최댓값보다 크게 주어지므로 사람들을 구출할 수 없는 경우는 없습니다. 입출력 예 people limit return [70, 50, 80, 50] 100 3 [70, 80, 50] 100 3 => 탐욕법으로 문제를 해결해야 합니다. => 2명만 보트에 탈 수 있다는 것을 염두에 둬야합니다. => 가장 무거운 사람을 limit에서 뺀 후, 남은 사람중 가장 가벼운 사람을 뺄 수 있는지 확인합니다. => 가장 가벼운 사람을 뺄 수 있다면 limit에서 뺍니다. => 위의 알고리..