📒활용개념

1.탐욕법을 활용하여 문제를 해결한다.
2. vector의 sorting을 활용한다.

📌문제설명

무인도에 갇힌 사람들을 구명보트를 이용하여 구출하려고 합니다. 구명보트는 작아서 한 번에 최대 2명씩 밖에 탈 수 없고, 무게 제한도 있습니다. 구명보트를 최대한 적게 사용하여 모든 사람을 구출하려고 합니다.

• 무인도에 갇힌 사람은 1명 이상 50,000명 이하입니다.
• 각 사람의 몸무게는 40kg 이상 240kg 이하입니다.
• 구명보트의 무게 제한은 40kg 이상 240kg 이하입니다.
• 구명보트의 무게 제한은 항상 사람들의 몸무게 중 최댓값보다 크게 주어지므로 사람들을 구출할 수 없는 경우는 없습니다.

📌구현

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

using namespace std;

int solution(vector<int> people, int limit) {
    int answer = 0;
    int min=0;									//people의 가장 작은 부분부터 확인
    int max=people.size()-1;					//people의 가장 큰 부분부터 확인
    
    sort(people.begin(), people.end());			//people을 sorting
    
    while(max>=min){
    	//people의 가장 큰 값과 가장 작은 값의 합이 limit보다 작은 경우
        if(people[max]+people[min]<=limit){	
            //다음 큰 값과 작은 값을 비교
            max--;
            min++;
            answer++;
        }
        else{
        	//큰 값만 혼자 작아진다. -> 혼자 보트를 타고간다.
            max--;
            answer++;
        }
    }
    
    return answer;
}

📌주의점

• sorting을 해야 문제를 쉽게 해결할 수 있다.
• 어떤 값과 어떤 값을 더할지 선택을 해야한다. ->가장 큰 값과 가장 작은 값