백준 BOJ 11256 : 사탕 - 파이썬

문제

당신은 사탕 공장의 주인이다. 날마다, 당신은 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()