[Programmers] Level2 : 구명보트

Question

---

Solution

• 2명만 보트에 탈 수 있기 때문에 가능한 최대 무게와 최소 무게를 태울 수 있도록 한다.
• 주어진 vector를 오름차순으로 정렬하고 i = size()-1 부터 for 루프를 돌았다.
• 최대 무게는 반드시 뽑아서 태우고 limit - max에 해당되는 최소 무게가 있다면 minIdx를 증가시킨다.
• 최종적으로 i == minIdx가 되면 모두 태웠다고 볼 수 있다.

---

Cord

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int solution(vector<int> people, int limit)
{
    // 가능한 최대 무게와 최소 무게를 묶어서 태운다.
    int answer = 0;

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

    // 큰 무게 부터 시작
    int minIdx = 0;
    for (int i = people.size() - 1; i != minIdx - 1; i--)
    {
        ++answer; // 보트 수 증가

        if (i == minIdx) { break; }  // 같은 곳을 가리키게 되면 종료

        int max = people[i];
        int min = people[minIdx];

        // 최소 무게가 (limit - max) 보다 작거나 같은 값 인지 확인
        if (limit - max >= min) { minIdx++; }
    }

    return answer;
}

int main()
{
    vector<int> people = { 70, 70, 60, 40, 40 };
    int limit = 110;

    int answer = solution(people, limit);
    cout << answer;

    return 0;
}

---

Result