[C++] level2 구명보트 42885

📌구명보트

/* 해당 문제 설명은 링크로 대체한다. */

📌풀이

문제에서 2명까지만 태울 수 있다고 명시되어 있다!
그렇기 때문에 2명까지만 고려하면 된다!

greedy하게 푸는 문제에 포함된 문제이다.

먼저 오름차순으로 정렬한다. 그러면 입출력 예시의 경우 50, 50, 70, 80으로 people이 정렬된다.

이 상태에서 idx를 옮겨가며 2명을 태울 수 있으면 태우고 못태우면 큰 값부터 태운다.

📌코드

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

int solution(vector<int> people, int limit)
{
    int answer = 0;

    sort(people.begin(), people.end()); //오름차순으로 정렬

    //input1 ex. 50, 50, 70, 80
    int idx = 0;
    while (people.size() > idx)
    {
        int back = people.back(); //가장 큰 값
        people.pop_back();
        if (people[idx] + back <= limit)
        {
            answer++;
            idx++; //둘 다 태웠으니까 idx++해서 다음 친구 태워
        }
        else
        { //가장 큰 값만 먼저 태워
            answer++;
        }
    }

    return answer;
}

---

회고
level2 까지 문제를 다 푼 상태이기 때문에 고득점 kit 문제 중 level1, level2에 대한 문제를 다시 풀어보는 연습을 하고 있다.
넘 오랜만에 다시 풀어서 다 까먹어서 처음에 접근을 정렬도 안하고 가장 작은 값부터 sum_wieght를 만들어주어 구하다가 비효율적인 것 같다는 생각을 했다. ㅋㅋ ㅋ ㅋ ㅋ ㅋ 늦게라도 비효율적이라고 느낀게 다행인건지 멍천한건지 모르겠당 ... ^^ .....
그래서 다시 처음부터 접근해서 위에처럼 풀었다 ....