[프로그래머스](Greedy) 구명보트 (C++)

구명보트(Level 2)

문제

전체 문제 보기

코딩테스트 연습 - 구명보트

접근법

문제에서 요구한 구명보트 개수의 최솟값을 구하기 위해서는 제한 무게를 넘지 않는다면, 가장 무거운 사람이 가장 가벼운 사람과 탑승해야 한다. 다음과 같은 상황을 생각해보자

보트의 무게 제한: 150kg
사람들의 무게: 100kg 80gk 60kg 50kg

가장 무거운 사람인 100kg인 사람이 가장 가벼운 50kg과 같이 탑승해야 보트를 가장 효율적으로 사용할 수 있다. 만약 80kg인 사람이 50kg인 사람과 탑승하게 되면, 100kg인 사람은 60kg인 사람과 함께 탑승할 수 없기 때문에 보트를 한번 더 운영해야 한다. 때문에 이번 문제는 "가장 무거운 사람이 가장 가벼운 사람과 탑승한다."라는 부분적인 최적의 해가 전체적인 최적의 해가 될 수 있는 그리디로 풀 수 있는 문제이다.

구현

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

using namespace std;

int solution(vector<int> people, int limit) {
    int answer = 0;
    // 사람들의 무게는 무작위로 들어오기 때문에 정렬하여 사용한다.
    sort(people.begin(), people.end(), greater<int>());

    // i: 가장 무거운 사람부터 탐색, 보트에 탑승시 ++
    // j: 가장 가벼운 사람부터 탐색, 보트에 탑승시 --
    for(int i = 0, j = people.size() - 1; i <= j; i++)
    {
        // 가장 무거운 사람과 가벼운사람의 무게합이
        // 보트의 제한보다 작다면, 가벼운사람도 함께 탑승
        if(people[i] + people[j] <= limit)
            j--;

        // 루프문을 돌 때 마다 보트 이용량++
        answer++;
    }
    return answer;
}