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

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

using namespace std;

int solution(vector<int> people, int limit) {
    int answer = 0;
    int start = 0;
    int end = people.size() - 1;
    
    //내림차순 정렬
    sort(people.rbegin(), people.rend());
    
    while(start <= end)
    {
        if(people[start] + people[end] <= limit)
        {
            start++;
            end--;
            answer++;
        }
        else
        {
            start++;
            answer++;
        }
    }
    
    
    return answer;
}

풀이

1. 내림 차순으로 정렬을 한다.

2. 큰 것과 작은 것의 합이 limit보다 작거나 같으면 두개를 소거

3. 큰 것만 허락된다면 큰 것만 소거 ( 구명 보트가 몸무게보다 큼 )

4. start가 end와 같거나 커지면 종료

 

 

 

 

 

 

 

https://programmers.co.kr/learn/courses/30/lessons/42885?language=cpp 

코딩테스트 연습 - 구명보트