[Leetcode 881번 문제] 881. Boats to Save People

문제 설명

사람 배열이라는게 존재함. 모든 사람들을 보트에 태워야한다. 보트에는 최대 2명이 탈 수 있고 그 두명의 무게의 합은 최대 중량 limit을 초과할 수 없다. 보트가 무한할때 이 인원들을 태울 수 있는 보트의 최소 숫자를 구해라.

입력

1이상 5만 이하의 사람배열

각 사람의 무게는 limit과 3만보다 작고 1보다 큰 정수이다

출력

정수, 보트의 최소 개수

과정

보트를 태운다.

배열이 나에게 아주 호의적인 상황이라면 (모든 탑승자의 크기가 limit / 2) 답은 뭐 나누기 2의 몫과 같음. 이 문제는 그렇지않음 보트의 수는 무한하다는것도 특징이다.

그럼 이상적인상황을 만드는 방법을 구해야했다.

 

각 보트에 탈 수 있는 인원은 2명이 최대니까

정렬해놓고 투포인터로 최소 무게 인원과 최대 무게 인원을 더해보는 방식을 선택하려고 했다

몸무게가 최소인 사람과 같이 탈 수 있는 사람은 많지만 가장 필요할 사람은 가능한 사람중에서 가장 
몸무게가 큰 사람일 것

 

이런 가정이 들어갔다

가장 작은수가 반드시 필요한 놈은 가장 큰 수라면 정렬해서 앞뒤를 확인하는 투포인터로 문제를 풀 수 있을것같았다.

알고리즘 개요도

알고리즘

class Solution {
public:
    int numRescueBoats(vector<int>& people, int limit) {
        if (people.size() == 1) return 1;
        sort(people.begin(), people.end());
        int start = 0, end = people.size() - 1;
        int ans = 0;
        while (start < end)
        {
            int canRideOnWith = limit - people[end];
            if (canRideOnWith > 0 && start < end && people[start] <= canRideOnWith)
            {
                canRideOnWith -= people[start++];
            }
            ans++;
            end--;
        }
        ans += start == end;
        return ans;
    }
};