[백준 11256번] 파이썬 - 사탕

백준 11256 - 사탕

시간 제한 1초, 메모리 제한 256MB

# 조건

• 당신은 사탕 공장의 주인이다.
• 날마다, 당신은 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번째 테스트 케이스에서 최소한의 상자 개수를 출력하여야 한다.

# 접근 방법

• 리스트로 입력받아 내림차순으로 정렬해도 되고 방법은 많은 문제였기에 나는 heapq를 사용하여 풀어주었다.
• 입력받는 상자의 크기를 음수로 하여 최대힙을 만들어주었다.
• J가 0보다 작아질 때 까지 HEAPPOP을 하며 상자의 개수를 카운트 해준다.

import sys  
sys.stdin = open('input.txt')  
input = sys.stdin.readline  
from heapq import heappop, heappush  

T = int(input())  
for _ in range(T):  
    J, N = map(int, input().split())  
    boxes = []  
    result = 0  
    for _ in range(N):  
        r, c = map(int, input().split())  
        heappush(boxes, -(r*c))  
    while J > 0:  
        val = heappop(boxes)  
        J += val  
        result += 1  
    print(result)