탐욕법(Greedy) > 구명보트

 

---

[ 풀이 ]

 

첨엔 그냥 풀다가 위에 보니까 보트에 탈 수 있는 사람이 2명으로 제한되었더라고

그래서 딱 생각한게 그럼 앞에서부터 비교하면서 둘이 합쳐서 limit를 안넘으면 보낼까?

하고 했는데 테스트 반은 통과를 못했더라고,,

그래서 염또구,,, 또 구글링했지모야

그랬더니 최대랑 최소를 묶어서 보내래 뭔말이야 했는데

이걸 벡터로 정렬하고, 뒤에서부터 차근차근 뺴는거지 어차피 젤 무거운 사람은 혼자 타야되는데 만약 가벼운애랑 태울수있으면 보내는거고 아님 말고~ 식으로

얘는 생각보다 쉽게 풀었다

근데 벡터를 많이 안써봐서 그거 검색했다ㅠ

 

vector.size( ) : 벡터 사이즈

vector.back( ) : 벡터 맨 뒤 값

vector.push_back( ) : 벡터 맨 뒤의 값 빼기

 

그렇게 완성된 코드,,,,ㅠㅠ

while문이랑 벡터 같은 자료구조 쓰는 연습을 좀 해야겠다

자료구조도 다시 공부해서 정리해야지ㅠㅠ

 

---

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

using namespace std;

int solution(vector<int> people, int limit) {
    int answer = 0;
    int index = 0;
    int max;
    sort(people.begin(),people.end()); //벡터 정렬
    while(people.size()>index)
    {
        max = people.back();
        people.pop_back();
        if(people[index]+max<=limit)
        {
            index++;
        }
        answer++;
    }
    return answer;
}