Lv2. 구명보트

코딩테스트 연습 > 구명보트

1. 풀이 설명

1. people 을 오름차순 정렬한다.

2. 가장 가벼운 사람을 가리키는 l과 제일 무거운 사람을 가리키는 r 이 l <= r 을 만족할 때까지 while문을 돌면서

3. 가벼운 사람 + 무거운 사람 무게가 limit 이하면 가벼운 사람도 보트에 탈 수 있기 때문에 l += 1 을 해주고, 그 외에는 무거운 사람만 보트에 탄다 (r -= 1).

4. boat의 개수를 반환한다.

2. 나의 풀이

def solution(people, limit):
    boat = 0
    people.sort()
    l = 0
    r = len(people) - 1
    while l <= r:
        if people[l] + people[r] <= limit:
            l += 1
        r -= 1
        boat += 1
    
    return boat

3. 배운점

1. people을 정렬을 한 후에 무조건 앞에서부터 2명씩 태우느라 한참을 헤맸던 문제다.
   몸무게가 제일 큰 사람과 제일 작은 사람을 매칭시켜서 태우는 방법이 보트를 가장 적게 띄울 방법이었다. 예를 들면 아래와 같다.

[10, 20, 30, 40], 50

[10, 20], [30], [40]  	-> boat 3개

[10, 40], [20, 30]		-> boat 2개

"탐욕법" 문제를 풀 때에서 어떤 경우가 가장 탐욕스러운 것인지를 정의하고 시작하자.
이 문제의 경우, 한 보트에 limit까지 무게를 최대화 하는 것이다.