[Python] 프로그래머스 42885. 구명보트 (Lv.2)

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

프로그래머스

 

기본적인 탐욕법(Greedy) 문제입니다.

그리디란 매 상황에서 최선의 선택을 하는 풀이를 말합니다. 이 문제에서 한 보트에는 최대 2명이 탈 수 있으며 2명의 무게합 제한도 있습니다.

 

이때 가장 적은 보트로 모든 사람을 태우는 방법은 무엇일까요?

우선 보트에 최대한 2명을 많이 태워야 한다는 아이디어는 바로 떠올릴 수 있습니다. 1명씩 태우는 것보다 2명을 태울때 마다 사용하는 보트의 수가 1씩 줄어들죠.

그럼 최대한 2명을 많이 태우려면 어떻게 해야 할까요?

정답은 짝지을 수 있는 무거운 사람을 가장 가벼운 사람과 짝짓는다 입니다. 예를 들어볼까요?

 

무게 제한이 10이고 4명의 무게가 [1, 2, 5, 6, 8] 이라고 해봅시다. 가장 무거운 무게가 8인 사람을 무게가 1인 사람과 짝지으면 한 보트에 태울 수 있습니다. 이 사실은 당연하지만 이때 이런 생각을 하시는 분도 있을겁니다. 무게가 8, 2인 둘을 태우면 더 가벼운 무게가 1인 사람을 남길 수 있는데 이 방법을 고려하지 않아도 될까요? 

 

 

반례를 찾아봅시다. 작은 무게가 먼저 나오게 정렬된 a, b, c, d 가 있습니다. (a <= b <= c <= d) 우리는 a + d 대신 b + d를 태워서 이득을 보는 경우를 찾으려고 합니다. 즉 a + c는 보트에 탈 수 있지만 b + c는 보트에 탈 수 없는 경우를 찾는겁니다.

그럼 우리는 제한 무게 limit가 존재할 때, a + c <= limit < b + c 가 되게 하는 값들을 찾는겁니다.

 

a, b, c, d의 무게 순서를 알기 때문에 c와 d의 정확한 차이는 몰라도 d보다 작거나 같은 c는 d - x (x >= 0)로 다시 쓸 수 있습니다. 위 식에 대입을 해보면 limit < b + d - x가 되어야합니다. 그런데 우리는 a + d 대신 b + d를 태우려고 하기 때문에 b + d <= limit 성립해야합니다. 즉 b + d <= limit이고 여기서 x를 뺀 b + d - x는 당연히 limit보다 작거나 같다는 사실을 알 수 있습니다.

 

따라서, b + d를 보트에 태울 수 있다면 b + c를 보트에 태울 수 있는것도 당연한 사실이 되고 두 조합을 모두 보트에 태울 수 있으므로 고려하지 않아도 됩니다. 주어진 무게들을 정렬 한 뒤 현재 가장 무거운 사람과 가벼운 사람을 묶어 태울 수 있다면 태우고, 불가능하다면 무거운 사람을 혼자 보트에 태우며 필요한 보트의 수를 카운팅하면 됩니다.

 

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