[BOJ]1256号:キャンディ


✔️ 質問する
あなたはキャンディ工場のボスです.毎日、あなたはJ個のキャンディを箱詰めして店に送ります.
あなたは大きさの異なる箱をN個持っています.便宜上、箱を最小限にしたいです.△箱をいっぱい詰める必要はありません.一部を満たすだけです.
工場から取り出したキャンディの数と箱ごとの大きさを入力し、最小限の箱の数を印刷するプログラムを作成します.キャンディを包装するのに十分な空間があることを保証します.
[入力]
第1行は、試験例の個数T(1≦T≦10)を与える.各テストケースは、次のフォーマットに従います.
試験箱の最初の行は、キャンディの個数Jと箱の個数Nを与える.(1 ≤ J, N ≤ 1,000)
次のN行において、各行は、iの第1のボックスの長手方向長さ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と比較します.論理設計自体が簡単な問題です.