[LeetCode] 881. Boats to Save People

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

leetcode - Boats to Save People

문제 유형 : 정렬, 그리디, 투 포인터

문제 난이도 : Medium

 

문제

You are given an array people where people[i] is the weight of the ith person, and an infinite number of boats where each boat can carry a maximum weight of limit. Each boat carries at most two people at the same time, provided the sum of the weight of those people is at most limit.

Return the minimum number of boats to carry every given person.

 

people[i]는 i번째 사람의 무게를 뜻한다. 보트는 무한정 사용가능하다.

보트는 최대 limit만큼 버틸 수 있다.

보트에 최대 두 사람이 탈 수 있다.

모든 사람을 구조할  보트의 최소 개수를 구하시오.

 

풀이

우선, people배열을 정렬한다.

투 포인터로 배열의 양 끝에서 시작한다.

두 합이 limit이내라면, left++와 right--를 동시에, 아니라면 더 무거운 right을 혼자 태우는 뜻으로 right--만 해준다.

중간에 보트의 수를 누적시켜주자.

 

코드

C++

#pragma GCC optimize("03", "unroll-loops");
static const int __ = [](){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();

class Solution {
public:
    int numRescueBoats(vector<int>& people, int limit) {
        sort(people.begin(), people.end());
        int ans = 0;

        int left = 0, right = people.size() -1;

        while(left <= right) {
            if(people[left] + people[right] <= limit) {
                left++;
                right--;
            } else {
                right--;
            }
            ans++;
        }

        return ans;
    }
};