✔️ 문제

당신은 사탕 공장의 주인이다. 날마다, 당신은 J개의 사탕을 가게에 보내기 위해 상자에 포장해야 한다.

당신은 크기가 다른 상자 N개를 가지고 있다. 당신은 편리를 위해 상자를 최소한으로 쓰려고 한다. (박스를 다 채울 필요는 없다. 일부분만 채워도 된다.)

당신이 공장에서 나오는 사탕의 개수와 각 상자의 크기를 입력받고, 상자를 최소한으로 쓸 때의 사용되는 상자 개수를 출력하는 프로그램을 작성하라. 사탕들을 포장할 공간은 충분하다는 것이 보장된다.

---

[입력]
첫 번째 줄에는 테스트 케이스의 개수 T (1 ≤ T ≤ 10)가 주어진다. 각각의 테스트 케이스는 아래 형식을 따른다.

테스트 케이스의 첫 번째 줄에는 사탕의 개수 J와 상자의 개수 N이 주어진다. (1 ≤ J, N ≤ 1,000)

다음 N개의 줄에는 각각 줄마다 i번째 상자의 세로 길이 Ri 그리고 가로 길이 Ci가 주어진다. 상자의 크기는 다른 상자의 크기와 똑같을 수도 있다. 상자에는 Ri * Ci보다 더 많은 사탕을 포장할 수 없다. (1 ≤ Ri, Ci ≤ 10,000)

[출력]
출력은 T개의 줄로 이루어진다. 각각의 줄마다 i번째 테스트 케이스에서 최소한의 상자 개수를 출력하여야 한다.

😎 소스 코드

T = int(input())
answer = []

for _ in range(T):
	candy, box = map(int, input().split())
	size = []
	
	# get box sizes
	for _ in range(box):
		R, C = map(int, input().split())
		size.append(R * C)
	
	size.sort(reverse=True)
	
	# find minimum box
	min = 0
	sum = size[0]
	
	for i in range(1, box+1):
		if sum < candy:
			min += 1
			sum += size[i]
		else:
			min +=1
			break
	answer.append(min)

for ans in answer:
	print(ans)

✊ 문제를 풀고 나서

상자 부피를 계산해서 리스트에 삽입한 뒤 내림차순으로 정렬해서 리스트의 첫번째 원소부터 candy와 비교했다. 로직 설계 자체는 간단한 문제였다.