https://codeforces.com/contest/1498/problem/B
시간 1초, 메모리 256MB

input :

• t (1 ≤ t ≤ 5 * 103)
• n W(1 ≤ n ≤ 105)(1 ≤ W ≤ 109)
• w1, w2, …, wn (1 ≤ wi ≤ 106)

output :

• Output t integers. The i-th integer should be equal to the answer to the i-th test case — the smallest height of the box.
  t개의 정수를 출력하시오. 각 테스트케이스에서 상자의 가장 작은 높이를 출력하시오.

조건 :

• You are given n rectangles, each of height 1. Each rectangle's width is a power of 2
  높이 1짜리의 직사각형을 n개 입력 받는다. 각 직사각형의 넓이는 2의 지수로 이루어져있다.

• You are also given a two-dimensional box of width W. Note that W may or may not be a power of 2. Moreover, W is at least as large as the width of the largest rectangle.
  W짜리 넓이의 상자를 입력받습니다. W는 2의 지수 일수도 있고 아닐 수도 있다. W는 최소한 직사각형들 중 가장 큰 거보다 크다.

---

입력 받은 W 길이의 상자를 채우는 것인데 이 높이가 가장 낮도록 채워야 한다.
입력 받은 예제에서도 첫 층을 8, 4, 2, 1로 채우지만
8, 8
4, 2, 1 이렇게 채울 수가 있다.

그러니까 각 층을 채울 때에 남은 공간을 채울 수 있는 가장 큰 조각을 집어넣는 거다.

최근에 봤었던 문제랑 비슷하게 그리디로 접근을 하는 것이 좋다.
이 공간에 들어갈 수 있는 것들 중 가장 큰 것을 찾아야 한다.

MAP

각 입력 받은 직사각형들의 개수를 기록해야 한다. 그리고 이를 통해 각 층에 빈 공간을 채울 수 있는지를 확인 할 것이다.
각 직사각형의 크기를 오름차순 순서대로 보기 위해서 입력 받은 것들을 시작 부터 정렬을 하고 딕셔너리에 저장을 하자.

예외

한 3가지 정도를 생각해야 한다.

각 층을 더 이상 채울 수 있는 직사각형이 없을 때 이럴떄는 now_add에 -float('inf')가 남아있을 것이다. 그렇기 때문에 for문을 사용하면 모든 경우를 보지 않을 수 도 있다. while문을 사용하자.

그리고 딕셔너리에 저장된 값이 0이 된다면 이 키를 삭제하도록 하자.
각 층의 남은 공간 remain 같은 경우에도 새로운 층으로 바뀔 때에ㅔ remain이 0이었다면 w로 그러지 않다면 새로운 층에 이 직사각형을 넣어야 하는 것이기에 w - now_add를 넣어준다.

마지막 한 층

remain의 길이가 w로 빈 층이라면 이 층을 빼줘야 한다.

import sys

for _ in range(int(sys.stdin.readline())):
    n, w = map(int, sys.stdin.readline().split())
    data = list(map(int, sys.stdin.readline().split()))
    temp = dict()
    data.sort()

    for item in data:
        if item not in temp:
            temp[item] = 1
        else:
            temp[item] += 1

    remain, ans, keys = w, 1, len(data)
    while keys > 0:
        now_add = -float('inf')
        for key in temp.keys():
            if remain < key:
                break
            now_add = key

        if now_add == -float('inf'):
            remain = w
            ans += 1
            continue

        remain -= now_add
        temp[now_add] -= 1

        if temp[now_add] == 0:
            del temp[now_add]

        if remain <= 0:
            ans += 1
            if remain == 0:
                remain = w
            else:
                remain = w - now_add

        keys -= 1

    print(ans - 1 if remain == w else ans)