프로그래머스_2단계_구명보트_C++

그리디 알고리즘을 활용하는문제

 

문제풀이:

#include <vector>
#include <algorithm>

using namespace std;

int solution(vector<int> people, int limit) {
    int answer = 0;
    
    sort(people.begin(), people.end()); // 사람들의 몸무게를 오름차순으로 정렬
    
    int left = 0; // 가장 가벼운 사람을 가리키는 인덱스
    int right = people.size() - 1; // 가장 무거운 사람을 가리키는 인덱스
    
    while (left <= right) {
        if (people[left] + people[right] <= limit) { // 두 사람의 무게 합이 제한 이하일 경우
            left++; // 가장 가벼운 사람과 가장 무거운 사람을 함께 태우고 다음 가벼운 사람으로 이동
        }
        right--; // 가장 무거운 사람은 항상 태웁니다.
        answer++; // 구명보트 개수 증가
    }
    
    return answer;
}