[백준] 11256 : 사탕 - Python

그리디 알고리즘

문제 해결
해당문제는 사탕을 채우는데 상자의 개수를 최소한으로 사용.
그러려면 상자의 면적 즉 row * col의 값을 data리스트에 저장한 후에 내림차순으로 정렬한 후 반복문을 통해 data리스트의 값을 하나씩 확인하면서 사탕의 개수에서 현재 확인하고 있는 상자의 크기를 빼고 count +=1 해주면 돼.
만약 사탕의 개수가 0이하일 경우 더 이상 상자에 넣을 사탕이 없으므로 반복문 종료하고 count 출력해주면 돼 (각 테스트마다)

소스코드

import sys


#J개의 사탕을 가게에 보내기 위해 상자에 포장
#크기가 다른 N개의 상자 상자 최소한으로 사용

T = int(input())
for _ in range(T):
    J, N = map(int, input().split()) #사탕의 개수, 상자의 개수
    data = []
    for i in range(N):
        row, col = map(int, input().split())  #세로, 가로
        data.append(row * col) 
        #row * col만큼보다 더 많은 사탕을 포장할 수 없다.
    #모든 상자를 다 넣었으면 이제 가장 큰것들부터
    count = 0
    data.sort(reverse=True)
    for i in range(N):
        J = J - data[i]
        count += 1
        if J <= 0:
            break
    print(count)