[Level 2] 구명보트

문제
무인도에 갇힌 사람들을 구명보트로 구출하려고 한다. 구명보트에는 최대 2명씩 밖에 탈 수 없고, 무게제한도 있다.
구명보트를 최대한 적게 사용하여 모든 사람을 구출하라.

입력
사람들의 몸무게를 담은 배열 people과 구명보트의 무게 제한 limit이 입력된다.
사람의 몸무게는 40kg이상 240kg이하
구명보트의 무게제한은 40kg이상 240kg이하

출력
모든 사람을 구출하기 위해 필요한 구명보트 개수의 최솟값을 출력한다.

---

접근

최대한 적게 구명보트를 사용하려면 한 번에 많은 사람을 태워야하고 그러기위해서는 몸무게가 작은사람과 몸무게가 큰사람을 비교해보면서 제한 이하라면 이동시켜야한다. 

 

그리고 문제에서 주어진 조건들을 모두 공격적으로 살펴 볼 필요가 있다. 그냥 주어지는 조건은 없다. 여기서 2명씩 밖에 타지 못한다는 것도 정렬 후에 투 포인터로 풀 수 있지 않을까라는 생각이 떠오를 수도 있다.

 

구현

먼저 입력받은 사람들의 무게를 오름차순으로 정렬한다.

left는 몸무게가 적게나가는 사람을 가리키고 right는 비교적 몸무게가 많이 나가는 사람을 가리킨다.

while문 안에서 몸무게를 비교했을 때

left와 right가 가리키는 사람의 몸무게 합이 limit 이하라면 left를 증가시키고 right를 감소시킨다.

그렇지 않다면 몸무게가 큰 사람을 먼저 태워주기 위해 right를 감소시킨다.

while문이 한 번 돌때마다 최종해인 answer를 1씩 증가시킨다.

def solution(people, limit):
    answer = 0
    people = sorted(people)
    left = 0
    right = len(people)-1
    while left <= right:
        if people[left] + people[right] <= limit:
            left += 1
        right -= 1
        answer += 1
    return answer