[Programmers] 구명보트

https://school.programmers.co.kr/learn/courses/30/lessons/42885

프로그래머스

0. Headers

#include <vector>
#include <algorithm>
using namespace std;

1. 알고리즘

 - 구명보트의 무게 제한은 항상 사람들의 몸무게 중 최댓값보다 크게 주어지므로 사람들을 구출할 수 없는 경우

   - 위 조건이 있으므로 정렬하고 앞과 뒤를 비교하면서 계산

int solution(vector<int> people, int limit) {
    int answer = 0;
    int front = 0, back = 0;
    
    sort(people.begin(), people.end());
}

 - 백터에서 마지막 값을 빼고 그 값과 처음 백터의 값을 더해 limit보다 작은 경우 통과

   - 통과되지 못하면 마지막 값만 나온 경우임

int solution(vector<int> people, int limit) {
    while(people.size() > front){
        back = people.back();
        people.pop_back();
        
        if(people[front] + back <= limit){ answer++; front++; }
        else answer++;
    }
}

2. 완성 코드

#include <vector>
#include <algorithm>
using namespace std;

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