[그리디 알고리즘] 11256번 - 사탕

[백준] 11256번 - 사탕

풀이 시간: 10~15분 이내

 

1) 문제 해결 아이디어

문제 설명대로 코드를 구현하기만 하면 풀 수 있는 쉬운 문제였다.

 

박스 크기(r, c)에 담을 수 있는 최대 사탕 개수는 (r * c)이다.

최소한의 상자 개수는 박스 부피(volume)가 큰 상자부터 사탕을 담는 것이다.

그래서 입력받은 상자(box)들을 부피 기준으로 내림차순 정렬해주었다.

 

2) 소스코드

t = int(input())  # 테스트 케이스 수

for i in range(t):
  j, n = map(int,input().split())  # 사탕 개수, 상자 개수
  box = []  # n개의 박스 크기
  res = 0 # 박스 개수
  for _ in range(n):
    box.append(list(map(int, input().split())))  # 세로, 가로 길이
    
  # 박스 부피 기준 내림차순 정렬
  box.sort(key=lambda x : x[0] * x[1], reverse = True)

  # 최소 박스 개수 세기
  for b in box:
    # 사탕이 0개가 되면 탈출
    if(j == 0):
      break
    volume = b[0] * b[1]  # 박스 부피
    if(j >= volume):
      j -= volume  # 박스 부피만큼 차감
      res += 1     # 박스 개수 추가
    else:
      j -= j  # 사탕 개수만큼 차감
      res += 1     # 박스 개수 추가
    
  print(res)  # 최소 박스 개수