[프로그래머스] 구명보트

---

🔗 문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/42885

프로그래머스

---

728x90

👩‍💻 코드

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

using namespace std;

int solution(vector<int> people, int limit) {
    sort(people.begin(), people.end());
    
    int i = 0;
    int j = people.size() - 1;
    int answer = 0;
    
    while (i <= j) {
        if (people[i] + people[j] <= limit) {
            i++;
        }
        
        j--;
        answer++;
    }
    
    return answer;
}

---

📝 풀이

가장 가벼운 사람과 가장 무거운 사람을 쉽게 선택하기 위해 people을 오름차순으로 정렬한다.

가장 가벼운 사람을 가르키는 포인터 👉 i
가장 무거운 사람을 가르키는 포인터 👉 j

가장 가벼운 사람과 가장 무거운 사람의 합이 limit 이하면 둘을 같은 보트에 태운다. 👉 포인터 모두 이동 (i++, j--)

합이 limit을 초과하면 무거운 사람만 보트에 태운다. 👉 무거운 사람 포인터만 이동(j--)

최종 보트 수 answer을 return 한다.