[프로그래머스] 구명보트 with C++

문제 설명

---

제한 사항 및 입출력 예제

---

개념

　이 문제는 최대 2명만 탑승 가능한 구명보트를 최소한으로 사용해 모든 사람을 구조하는 문제다. 이러한 상황에서 구명보트의 수를 최소화하려면, 남은 사람들 중 가장 가벼운 사람과 가장 무거운 사람을 동시에 태울 수 있는지 확인하면 된다. 따라서 투 포인터 알고리즘을 이용하여, 매 순간 보트에 최대한 많은 사람을 태우는 그리디 알고리즘을 구현하면 문제를 해결할 수 있다. 

 

• 가장 가벼운 사람과 가장 무거운 사람이 보트의 무게 제한 내에 함께 탈 수 있다면, 두 사람을 동시에 태우는 것이 최선의 선택
• 그렇지 않다면, 가장 무거운 사람만 보트에 태우는 것이 최선의 선택

 

---

풀이

#include <vector>
#include <algorithm>
using namespace std;

int solution(vector<int> people, int limit) 
{
    sort(people.begin(), people.end());

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

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

    return answer;
}

　투 포인터 알고리즘을 사용하기 위해 주어진 벡터를 오름차순으로 정렬한다. 벡터를 양 방향에서 순회하며 <개념>에서 설명한 알고리즘을 이행하면 된다.