문제
당신은 사탕 공장의 주인이다. 날마다, 당신은 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번째 테스트 케이스에서 최소한의 상자 개수를 출력하여야 한다.
예제 입력 1
1
20 5
3 4
2 5
1 8
3 3
2 5
예제 출력 1
2
예제 입력 2
2
12 3
2 7
1 5
3 2
20 3
2 7
1 5
3 2
예제 출력 2
1
2
알고리즘 분류
- 그리디 알고리즘
- 정렬
제출 코드
def function():
T = int(input()) # 테스트 케이스 수
for _ in range(T): # 테스트 케이스 수 만큼 반복
J, N = map(int, input().split())
boxSize = []
count = 0
for i in range(N):
R,C = map(int, input().split()) # 상자 가로세로 길이를 입력받아 저장
boxSize.append(R * C) # 상자크기 (가로*세로)
boxSize.sort(reverse=True) # 상자크기를 내림차순으로 정렬
while J > 0:
J -= boxSize[count] # 사탕을 박스에 넣었으니 사탕갯수를 박스사이즈만큼 빼기
count += 1 # 상자가 1개 쓰였으니 카운트세기
print(count)
if __name__ == "__main__":
function()