[C++/프로그래머스] 구명보트

✅ LV. 2
🔖 그리디

✏️ 1차 솔루션

1. people 오름차순 정렬
2. people 이 n 명일 경우, 최소한 필요한 보트의 개수는 n 이 짝수면 n/2, n 이 홀수면 n/2+1 개 필요
   ➡️ 최소 개수부터 이 보트로만 모든 사람을 태울 수 있는지 확인하고 못 태우면 개수 늘려서 다시 확인
3. people 을 0번째 인덱스부터 2명씩 나눠서 태우는데 1명을 태울 때마다 limit 을 넘어가는지 확인하고 해당 인덱스 방문 표시
4. 새로운 보트에 태울 때마다 answer++
5. 할당된 보트 개수를 다 썼는데 모든 사람을 태우지 못했다면 다음 개수로 탐색

🚨 1차 trouble

최소값부터 채운다고 가장 효율적인 조합이 되는 것이 아니라는 것을 고려하지 못했으나 어떻게 구현해야 할지 모르겠음

✏️ 최종 솔루션

❗️ people 의 최대무게가 혼자 보트에 탈 가능성이 가장 높음

1. 최대무게가 다른 사람과 함께 보트에 타려면 최솟값과 탈 수 있기 때문에 함께 탈 수 있는지 확인
   ➡️ 최대무게+최소무게 <= limit 이면 idx++ , answer++
idx : 현재 최소 무게 표시하기 위함. 0부터 시작
2. 한번 확인한 후에는 pop_back 해서 최대값 지워줌
3. idx<people.size(): 이 과정을 최소값이 최대값과 동일해지기 전까지 반복

✏️ 최종 code

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

using namespace std;

int solution(vector<int> people, int limit) {
    int answer = 0;
    
    sort(people.begin(),people.end());
    
    int idx=0;
    while(idx<people.size()) {
        if(people[idx]+people.back()<=limit) {
            answer++;
            idx++;
        }
        else answer++;
        people.pop_back();
    }
    
    return answer;
}