백준 11256 : 사탕 (그리디)

www.acmicpc.net/problem/11256www.acmicpc.net/problem/11256

11256번: 사탕

 

N개의 상자로 J개의 사탕을 포장해야함(최소 상자)

 

Input: J, N (사탕 갯수, 상자 크기)

Output : 최소로 필요한 상자의 수

 

사탕 갯수와 상자의 용량을 인풋으로 받는다.

상자의 인풋은 [list(map(int,input().split())) for _ in range(N)] 으로 받으면 for문 없이 받아줄 수 있다.

가장 용량이 큰 상자부터 사용하며, 남아있는 사탕의 수를 세어준다.

 

import sys
input = sys.stdin.readline

def solve(J,boxes):
	# 각 박스에 담을 수 있는 최대 사탕수를 큰 순으로 나열
    boxes = sorted(boxes,reverse=True)
    ans = 0
    while J>0: # 포장 할 사탕이 남아있으면
    	# 가장 큰 상자부터 사탕을 포장하고
        packed = boxes.pop(0)
        # 남은 사탕의 갯수를 세준다
        J = J-packed
        ans += 1
    return ans
    

if __name__=='__main__':
    T = int(input())
    answers = []
    for t in range(T):
        J,N = map(int,input().split())
        boxes = []
        for i in range(N):
            r,c = map(int, input().split()) # r : 세로, c: 가로
            boxes.append(r*c) # box에 담을 수 있는 사탕의 갯수
        answers.append(solve(J, boxes))
    for ans in answers:
        print(ans)
    

인풋 형식을 sys.stdin.readline으로 바꿨더니, 같은 코드인데 280ms에서 60ms가 됐다.