[Programmers] 구명보트

[Programmers] 구명보트

Problem URL : 구명보트

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

using namespace std;

int solution(vector<int> people, int limit) {
    int total = people.size();
    int answer = total;
    sort(people.begin(),people.end()); //[1]
    int idx = 0;
    int ridx = total - 1;
    int half = limit / 2;
    while(idx < total && ridx > idx && people[idx] <= half) {
        while(ridx > idx) {
            if(people[idx] + people[ridx] <= limit) {
                answer--;
                break;
            }
            ridx--;
        }
        idx++;
        ridx--;
    }
    return answer;
}

Comments

[1] 두명이 타려면 작은 쪽이 절반이하의 몸무게여야한다.

작은 몸무게부터 탐색해서 남은 사람중 최대한 무거운 사람을 같이 태운다.(그리디)