Programmers / 구명보트 / C++

*문제 출처는 프로그래머스에 있습니다.

 

문제 제목: 구명보트 (2단계)

문제 사이트: https://school.programmers.co.kr/learn/courses/30/lessons/42885

프로그래머스

 

문제 설명

 

---

 

나의 풀이

 

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

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

 

 

이 문제는 탐욕 알고리즘을 사용해서 푸는 문제다.

문제를 풀 때 가장 무거운 사람과 가벼운 사람을 태워서 100kg이하라면 같이 보내고 100kg를 초과하면 무거운 사람만 먼저 보내는 방식을 사용하면 된다.

---

※ 알아야 할 것

 

탐욕 알고리즘 을 이용하여 정렬하고 제일 무거운 사람(맨 뒷사람)과 처음에 앉을 사람을 같이 보내면 된다.