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

#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 i = 0, j = people.size()-1;
    
    while(j > i){
        if(people[i] + people[j] <= limit) i++;
        answer += 1;
        j--;
        if(j == i){
            answer += 1;
            break;
        }
    }
    return answer;
}

i 는 0부터 시작하고 j는 제일 끝에서부터 시작해서 

가벼운 사람과 뚱뚱한 사람을 태우면 가장 최소 보트 개수를 얻을 수 있다.

만약 두 사람을 모두 태울 수 있다면, i += 1 을 하여 가벼운 사람을 옮겨준다. 

그렇지 않다면, 같이 탈 수 있는 j가 나타날 때 까지, j만 태워서 보낸다.

 

두 경우의 모두 answer += 1, j -= 1을 한다.

 

마지막에는, i j 가 딱 맞아 떨어지거나 i가 혼자 남는 경우 두 가지이다.

만약 i, j가 맞아 떨어지면 while문의 조건 i < j에 해당하지 않아서 while문을 나오게 되고

i가 혼자 남으면 j == i if문에 해당되고 혼자 남은 i를 태울 보트가 추가되고 while문을 나온다.