[백준] 사탕 : 11256번 - Python

https://www.acmicpc.net/problem/11256

11256번: 사탕

 

 

 

문제의 접근 방법

 

포장할 수 있는 사탕의 개수 = 상자의 크기(가로길이 * 세로길이)

"상자의 크기를 내림차순으로 정렬"

 

 

 

문제 풀이 방법

 

테스트 케이스 T개 입력 받기 -> T번만큼 반복문을 돌려 사탕의 개수(J), 상자의 개수(N) 입력 받기 -> N번만큼의 반복문을 돌려 상자의 가로(c)와 세로(r)길이를 입력받아 이 두 값을 곱한 값을 빈 리스트 arr에 저장하기 -> 리스트 arr를 내림차순으로 정렬(최소한의 상자를 사용하기 위해) -> 사탕의 개수(J)가 리스트 arr의 i번째까지 원소의 합보다 작거나 같으면 해당 인덱스를 출력하기 (그게 필요한 최소한의 상자의 개수를 나타냄)!

 

 

 

소스코드

T = int(input())

for _ in range(T):
    J,N = map(int, input().split())

    arr = []

    for _ in range(N):
        r,c = map(int, input().split())
        arr.append(r*c)

    arr.sort(reverse=True)

    for i in range(len(arr)):
        if J <= sum(arr[:i]):
            break   
    print(i)