[Leetcode] 881. Boats to Save People

문제 : https://leetcode.com/problems/boats-to-save-people/description/

---

people이라는 배열이 주어지는데, people[i]는 i번째 사람의 몸무게를 나타냅니다.

그리고 무게 제한이 limit인 무수히 많은 보트가 있습니다.

각 보트는 최대 limit 무게까지 운반할 수 있으며, 최대 두 사람이 탈 수 있으며 두 사람의 무게 합이 limit 이하여야 합니다.

주어진 모든 사람을 운반하기 위해 필요한 최소 보트 수를 구하세요.

---

한 번에 두 명이 탈 수 있습니다. 투포인터로 해결할 수 있습니다.

먼저 people 배열을 오름차순 정렬합니다. 왼쪽부터 탐색하는 left 인덱스, 오른쪽부터 탐색하는 right 인덱스를 준비합니다.

만약 한 보트에 가장 무거운 사람(people[right])이 탔을 때, 가장 가벼운 사람(people[left])이 같이 탈 수 없다면 가장 무거운 사람은 혼자 타야 합니다. 

즉, 남아있는 사람들 중 가장 무거운 사람과 가장 가벼운 사람이 함께 보트에 탈 수 있다면 (people[left] + people[right] <= limit) 같이 탑승하고, 불가능하다면 가장 무거운 사람만 보트에 탑승합니다.

이와 같은 방법으로 모든 사람들을 보트에 태웠을 때, 보트 수가 정답이 됩니다.

 

시간복잡도는 O(N).

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/medium/881.%20Boats%20to%20Save%20People.cpp