[알고리즘] 침몰하는 타이타닉(그리디)

(문제) 침몰하는 타이타닉(그리디)

---

유럽에서 가장 유명했던 유람선 타이타닉이 침몰하고 있습니다.

유람선에는 N명의 승객이 타고 있습니다.

구명보트를 타고 탈출해야 하는데 타이타닉에 있는 구명보트는 2명 이하로만 탈 수 있으며, 보트 한 개에 탈 수 있는 총 무게도 M kg 이하로 제한되어 있습니다.

N명의 승객 몸무게가 주어졌을 때 승객 모두가 탈출하기 위한 구명보트의 최소개수를 출력하는 프로그램을 작성하세요.

입력설명

첫째 줄에 자연수 N(5<=N<=1000)과 M(70<=M<=250)이 주어집니다.

두 번째 줄에 N개로 구성된 몸무게 수열이 주어집니다.

몸무게는 50이상 150이하입니다.

각 승객의 몸무게는 M을 넘지는 않습니다.

즉 탈출을 못하는 경우는 없습니다.

출력설명

첫째 줄에 구명보트의 최소 개수를 출력합니다.

테스트케이스

입력예제	출력예제
5 140 90 50 70 100 60	3
10 150 86 95 107 67 38 49 116 22 78 53	5

---

해결방법

몸무게가 가장 무거운 사람의 기회 비용은 몸무게가 가장 가벼운 사람과 같이 타야 효율적이다.

그래서 내림차 순으로 정렬한 뒤, 맨 마지막 인덱스에 있는 사람의 몸무게를 더한게 최대 몸무게 보다 크면 맨앞과 맨뒤를 빼고,

만약 넘는다면, 맨 앞에 있는 것만 뺀다.

---

코드

n, m = map(int, input().split())

arr = list(map(int, input().split()))

arr.sort(reverse=True)

count = 0

while arr:
    current = arr.pop(0)
    if arr and current + arr[-1] <= m:
        arr.pop()
    count = count + 1

print(count)