구명보트(Level2)

• 문제 링크: 코딩테스트 연습 > 탐욕법(Greedy) > 구명보트

• 문제 이해

  1. 주어진 수용 무게보다 작도록, 인원을 태울 수 있는 보트의 최대 개수를 구합니다.
  2. 이 때, 수용 가능 인원은 두명입니다.

• 알고리즘 구현

  1. 인원이 두명으로 제한되어있으므로, 두명이 보트에 탑승한 경우와 한명이 탑승한 경우로 나뉩니다.
  2. 두명이 탑승한 경우는 두 인원의 무게 합이 limit 보다 적은 경우입니다. 따라서, 두 인원을
     매칭하는 기준을 고려해야합니다.
  3. 저는 효율적으로 매칭하는 방법은, 무게가 가장 무거운 사람과 가장 가벼운 사람을 연결해보는
     것이라고 생각했습니다. 만약, 가장 가벼운 사람과 가장 가벼운 사람이 함께 보트에 탈 수 없다면,
     가장 무거운 사람은 혼자 탈 수 밖에 없기 때문입니다.
  4. 따라서 먼저 people을 정렬하고, 가장 무거운 사람 + 가장 가벼운 사람이 limit 보다 작은
     경우, 두명을 탑승 시키고 보트 한 대를 카운트하고, 가장 무거운 사람 + 가장 가벼운 사람이
     limit 보다 큰 경우, 혼자 탑승하고, 보트 한 대를 카운트합니다.

• 알고리즘

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int solution(vector<int> people, int limit) {
    int answer = 0;
    int n = people.size();
    int end = n - 1;
    int beg = 0;
    sort(people.begin(), people.end(), greater<int>());
    while (beg <= end) {
        if (people[beg] + people[end] <= limit) {
            ++beg;
            --end;
            answer += 1;
        }
        else {
            ++beg;
            answer += 1;
        }
    }
    return answer;
}