[Inflearn] PS - 004

문제 출처 : inflearn <파이썬 알고리즘 문제풀이(코딩테스트 대비)>

침몰하는 타이타닉(그리디)
유럽에서 가장 유명했던 유람선 타이타닉이 침몰하고 있습니다. 유람선에는 N명의 승객이 타고
있습니다. 구명보트를 타고 탈출해야 하는데 타이타닉에 있는 구명보트는 2명 이하로만 탈 수 있
으며, 보트 한 개에 탈 수 있는 총 무게도 M kg 이하로 제한되어 있습니다.
N명의 승객 몸무게가 주어졌을 때 승객 모두가 탈출하기 위한 구명보트의 최소개수를 출력하는
프로그램을 작성하세요.

▣ 입력설명
첫째 줄에 자연수 N(5<=N<=1000)과 M(70<=M<=250)이 주어집니다.
두 번째 줄에 N개로 구성된 몸무게 수열이 주어집니다. 몸무게는 50이상 150이하입니다.
각 승객의 몸무게는 M을 넘지는 않습니다. 즉 탈출을 못하는 경우는 없습니다.

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

▣ 입력예제 1
5 140
90 50 70 100 60

▣ 출력예제 1
3

풀이

'''
접근
1. 몸무게 리스트를 오름차순으로 정렬한다.
2. 첫 값부터 하나씩 더해가면서 m과 비교한다.
3. 더한 값(weight)이 140을 초과할 시 count(cnt)를 하나 올린다.
4. cnt를 출력한다.

최초 구상과 달라진 점
1. 두 명 이상 타지 못한다.
2. 따라서 오름차순으로 정렬한 몸무게의 첫 항을 기준으로 한다.
3. 첫 항과 마지막 항(가장 작은 몸무게)이 m보다 작다면 둘이 묶어서 한 배로 보낸다.
4. 마지막 항은 list.pop()으로 날린다.
5. 만약 묶었을 때 몸무게가 초과하면 날리지 않고 무거운 사람만 보낸다.
6. 각각의 과정에서 cnt를 하나씩 올린다.

난점
1. 문제 제대로 안 읽어서 조건을 빠트림.
2. 변수 관리 제대로
'''

import sys
# sys.stdin=open("input.txt", "r")

n, m = map(int, input().split())
a = list(map(int, input().split()))
weight = 0
cnt = 0
people = 0
a.sort(reverse=True)

for i in a:
    a.sort(reverse=True)
    if i == m:
        cnt += 1
    elif i != m:
        if i + a[-1] <= m:
            a.pop(-1)
            i = 0
            cnt += 1
        elif i + a[-1] > m:
            cnt += 1
            i = 0


print(cnt)