[프로그래머스][Python] 구명보트

문제를 정리해보자.

 

구명보트를 이용해 모두를 탈출시켜야 한다.

구명보트에는 최대 2명이 탑승한다. 탑승자의 무게 합이 제한을 초과하면 안 된다.

 

모든 사람을 구출하는 데 필요한 구명보트의 최솟값을 구해야 한다.

 

 

풀이를 생각해보자.

 

1. 두 사람이 타는 경우

(가장 무거운 사람 + 가장 가벼운 사람)이 무게 제한을 초과하지 않으면 둘 다 태운다.

한 번 태운 사람은 두 번 다시 태우지 않는다.

 

2. 한 사람이 타는 경우

(가장 무거운 사람 + 가장 가벼운 사람)이 무게 제한을 초과한다면,

가장 무거운 사람만 태운다.

 

 

혼자서 무게 제한을 넘기는 경우는 없다.

 

 

3. 마지막 사람

 

 

 

 

50은 70, 80이 나갔기 때문에 배열에 혼자 남겨졌다.

따라서 가장 무거운 사람도 아니고, 가장 가벼운 사람도 아니다.

이 경우는 '마지막 사람'이라고 생각한다.

 

 그냥 내보내면 된다.

 

 

구현해보자.

 

몸무게를 담은 배열을 오름차순으로 정렬한다.

 

i = 0

j = 배열 길이 - 1

 

1. 두 사람이 타는 경우 : i += 1, j -= 1

2. 한 사람이 타는 경우 : i += 1

3. 마지막 사람 : i += 1

 

 

def solution(people, limit):
    people.sort(reverse=True)

    i = 0
    j = len(people) - 1

    answer = 0

    while i <= j:
        # 마지막 사람
        if i == j:
            i += 1

        # 2개
        elif people[i] + people[j] <= limit:
            i += 1
            j -= 1

        # 1개
        else:
            i += 1

        answer += 1

    return answer


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