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

프로그래머스

구명보트의 한계 중량, 사람들의 몸무게를 입력 받을 때, 모든 사람을 구하기 위해 필요한 구명보트의 수를 구해주세요.

 

 

풀이 방법

가장 무거운 사람과 가장 가벼운 사람을 같이 태울 수 있는지 체크하며 진행합니다.

 

ex) Limit = 100

[30, 50, 50, 70, 80, 90], answer = 0;

가장 가벼운 30과 가장 무거운 90은 Limit을 넘기 때문에 같이 태울 수 없습니다.

즉, 90은 무조건 혼자만 타야하니 90만 제외해줍니다.

(90kg은 10kg이하의 사람과 같이 타야하는데 30kg이 가장 가벼운 몸무게이니 90kg과 같이 태울 수 있는 사람은 없다고 판단)

 

[30, 50, 50, 70, 80], answer = 1;

30과 80도 같이 태우는게 불가능 합니다. 그렇기에 80만 태워서 보내줍니다.

 

[30, 50, 50, 70], answer = 2;

30과 70은 같이 태우는게 가능합니다. 이번에는 둘을 태워서 보내줍니다.

 

[50, 50], answer = 3;

50과 50도 같이 태우는게 가능합니다. 이번에도 둘을 태워서 보내줍니다.

 

answer = 4;

구명보트의 최소 필요 수는 4개가 됩니다.

 

정리해보면 가장 큰 몸무게는 항상 제외시키고 있고, 경우에 따라서 가장 가벼운 몸무게도 같이 제외하고 있습니다.

 

정답 코드

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

using namespace std;


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

    while (idx < people.size())
    {
        int back = people.back();
        people.pop_back();
        
        if (back + people[idx] <= limit)
            idx++;
        
        answer++;
    }
    
    return answer;
}