백준 온라인 저지, 자료구조 / 23843번: 콘센트 (파이썬 / , 백준 골드문제)

문제

광재는 전자기기 대여사업을 시작했다. 퇴근하기 전에 다음날 손님들에게 빌려줄 N개의 전자기기를 충전하려 한다. 사용 가능한 콘센트는 M개가 있고, 성능은 모두 동일하다.

전자기기들은 한 번에 하나의 콘센트에서만 충전이 가능하고, 충전에 필요한 시간은 2^k(0 ≤ k ≤ 15, k는 정수) 형태이다.

광재의 빠른 퇴근을 위해 모든 전자기기를 충전하기 위한 최소 시간이 얼마인지 알려주자.

입력

첫째 줄에 전자기기의 개수 N과 콘센트의 개수 M이 주어진다. (1 ≤ N ≤ 10,000, 1 ≤ M ≤ 10)

둘째 줄에 충전에 필요한 시간 t_i를 나타내는 N개의 정수가 주어진다. (2⁰ ​≤ t_i ≤ 2¹⁵, t_i = 2^k (0 ≤ k ≤ 15, k는 정수))

출력

충전에 필요한 최소 시간을 출력한다.

제한

예제 입력 1

5 2
1 4 4 8 1

예제 출력 1

9

힌트

접근 방법

- 전자기기의 충전 필요시간을 내림차순으로 정렬한 뒤 콘센트 별 충전 min heap에 저장하여 하나씩 데이터를 빼면서 현재 탐색 중인 시간을 추가한다.
- 모든 탐색이 끝나고, 최대 시간을 출력한다.

코드

# https://www.acmicpc.net/problem/23843
# 접근 방법
# 전자기기의 충전 필요시간을 내림차순으로 정렬한 뒤 콘센트 별 충전 min heap에 저장하여 하나씩 데이터를 빼면서 현재 탐색 중인 시간을 추가한다.
# 모든 탐색이 끝나고, 최대 시간을 출력한다.
import heapq
n, m = map(int, input().split())
arr = list(map(int, input().split()))
arr.sort(reverse = True)
minHeap = []
for _ in range(m):
    heapq.heappush(minHeap, 0)
for t in arr:
    x = heapq.heappop(minHeap)
    heapq.heappush(minHeap, x+t)
print(max(minHeap))