[BOJ] 11256 - 사탕 (Python)

 

 

아이디어

 

상자 넓이를 기준으로 상자들을 내림차순 정렬한 후, 차례로 사탕 개수에서 상자 넓이 값을 뺀다.

 

 

풀이

 

import sys

input = sys.stdin.readline

def solution():
    T = int(input())
    for t in range(T):
        J, N = map(int, input().split())
        boxes = sorted([tuple(map(int, input().split())) for _ in range(N)], key=lambda x: -x[0]*x[1])
        res = 0
        for R, C in boxes:
            J -= R*C
            res += 1
            if J <= 0:
                break
        print(res)

solution()