[프로그래머스/파이썬] 그리디 구명보트

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

---

알고리즘 분류

• 그리디

문제풀이

구명보트는 한 번에 최대 2명까지 밖에 탈 수 없다는 것이 핵심이다.

people을 내림차순으로 정렬하고 가장 몸무게가 큰 사람과 제일 작은 사람과 비교해서 limit안에 들어오면 기본 구명보트 개수(사람의 수)에서 1씩 빼준다.

만약 limit보다 크다면 start사람은 그냥 혼자 구명보트를 타고 다음 사람으로 넘어간다.(start+=1)

참고:https://train-validation-test.tistory.com/entry/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EA%B5%AC%EB%AA%85-%EB%B3%B4%ED%8A%B8-level-2-%ED%8C%8C%EC%9D%B4%EC%8D%AC?category=859210

소스코드

def solution(people, limit):
    people.sort(reverse=True)
    
    start,end=0,len(people)-1
    
    result=len(people)
    while start<end:
        if people[start]+people[end]<=limit:
            result-=1
            end-=1
        start+=1
    
    return result