• 문제에 나름 강조까지 해놓았지만 놓치기가 쉬운데.. 한 보트에는 최대 두명까지만 탈 수 있다.
  • 사실, 이런 제한이 없다면 NP-complete 문제가 될 것이다..
• 보트에 탈 수 있는 인원이 최대 두명이므로, 두명이 탄 보트를 최대한 많이 만들면 된다.
• 구체적으로는 그리디한 방식으로, 가장 무거운 사람부터 시작해서 그 사람과 함께 보트에 타는 것이 가능한 사람이 있으면, 그 두명을 보트에 태워 보내는 것을 반복하면 최적해를 찾을수 있다.
  • 가장 무거운 사람과 같이 태울수 있는 사람이 있는데도, 그냥 무거운 사람 혼자 태워 보내는 것이 더 최적해가 될수 있다고 가정하면 모순이 생긴다.
• 가장 무거운 사람과 같이 태울 수 있는 사람을 찾는 것은, 그냥 가장 가벼운 사람을 테스트해보면 된다.
  • 같이 태울수 있는 사람중에서 굳이 가장 무거운 사람을 찾지 않고, 그냥 아무나 찾아도 최적해가 보장된다.
• 이 방법을 구현하려면, 그냥 무게순으로 정렬한 뒤에, 양쪽 끝(가장 가벼운 쪽과 가장 가벼운 쪽)에서부터 포인터를 증가/감소 시켜나가면서 비교하면 된다. 양쪽 끝값을 더했을때 limit보다 작으면 두명을 태우니까 양쪽 포인터를 모두 이동시키고, limit보다 크면 무거운 한명만 태우는 거니까 무거운쪽 포인터만 이동시킨다.
• 결국 O(nlogn)에 정렬한뒤, O(n)의 리니어 서치만으로 풀수 있다. 총 시간 복잡도는 O(nlogn)
• 실제로 구현한 아래 코드에서는, l==r 일때에는 한명만 남은 상태이므로 people[l]+people[r]을 비교하지 않고 그냥 남은 한명을 태워보내는 것이 논리적으로 맞지만, 그냥 저렇게 비교해서 처리하더라도 답은 달라지지 않는다.

"""Solution code for "Programmers 42885. 구명보트".

- Problem link: https://programmers.co.kr/learn/courses/30/lessons/42885
- Solution link: http://www.teferi.net/ps/problems/programmers/42885
"""


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

    return answer