[Programmers] - 구명보트

[Programmers] - 구명보트

 

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

프로그래머스

문제 이해

---

구명보트를 최대한 적게 사용하여 많은 사람들을 나르고 싶다.

보트가 견디는 무게가 100kg 이고 사람들의 몸무게가 다음과 같다면 [70kg, 50kg, 80kg, 50kg] 50+50 / 70 / 80 위와 같은 식으로 탈 수 있는 것이다.

 

알고리즘

---

그리디 알고리즘과 투포인터를 사용하여 풀었다.

가장 큰 무게를 가진 사람이 가장 무게를 적은 사람을 데리고 가야한다. 이 보다 더 적절한 사람은 존재하지 않기 때문

이를 통해 무게가 작은 사람을 Left , 현재 큰 무게를 가진 사람을 Right로 하여 Left < Right인 경우에 대해서 돌려주면 된다.

1. Left , Right Init

2. Left+Right를 할 때 Limit 값을 초과한다면 Right만 선택

3. 초과하지 않는다면 Left도 선택

4. 2~3반복

 

코드

---

#Programmers 구명보트

def solution(people, limit):
    answer = 0
    people.sort()

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

print(solution([70, 30 , 50, 80, 50],100))