[그리디] 구명보트 문제

구명보트를 최소한으로 사용하여 사람들을 구출하는 문제

사람들의 몸무게를 정렬한 후,
가장 가벼운 사람과 가장 무거운 사람을 조합하여 구명보트에 태우는 방식으로 접근할 수 있음

def solution(people, limit):
    # 사람들의 몸무게를 오름차순으로 정렬
    people.sort()
    
    # 구명보트를 사용할 개수를 저장할 변수
    boat_count = 0
    
    # 두 포인터를 사용하여 가장 가벼운 사람과 가장 무거운 사람을 선택
    light = 0  # 가장 가벼운 사람의 인덱스
    heavy = len(people) - 1  # 가장 무거운 사람의 인덱스
    
    # 두 포인터가 교차할 때까지 반복
    while light <= heavy:
        # 가장 가벼운 사람과 가장 무거운 사람의 무게 합이 limit 이하인지 확인
        if people[light] + people[heavy] <= limit:
            # 태울 수 있다면 두 사람을 태우고 두 포인터를 이동
            light += 1  # 가벼운 사람 인덱스 증가
            heavy -= 1  # 무거운 사람 인덱스 감소
        else:
            # 태울 수 없다면 가장 무거운 사람만 태우고 무거운 사람 인덱스 감소
            heavy -= 1
        
        # 매번 보트를 하나 사용하므로 보트 개수 증가
        boat_count += 1
    
    return boat_count  # 최종적으로 사용한 보트 개수를 반환