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

풀이

보트는 최대 두명씩 탈 수 있기 때문에 무거운 순과 가벼운 순으로 짝을 맞추어 주면된다.

a>=b>=c>=d라고 할때 {a,d} {b,c}로 짝은 맞추어준다.
a+d <= limit이라고 할때 c+d = (a-n) + (d+n) 은 항상  limit보다 작거나 같다. n은 0이상
a+d가 limit보다 크다면 큰 사람은 a는 보트에 혼자타야한다. 
큰 사람에서 작은 사람순으로 가르키는 idx2 와 역순인 idx1을 통해 짝을 맞추어준다.

#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 people_size = people.size();
    int idx1=0;
    int idx2=people.size()-1;
    int s_i=0;
    
    while(true){
        if(idx1>=idx2)
            break;
        if(people[idx2]+people[idx1]<=limit){
            people[idx2]+=people[idx1];
            idx1++;
            idx2--;
        }
        else{
            idx2--;
        }
    }
    
    answer=people.size()-idx1;
    return answer;
}