[백준/파이썬] 23843번 콘센트

문제

 

23843번 콘센트

 

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

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

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

 

입력

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

둘째 줄에 충전에 필요한 시간 $t_{i}$를 나타내는 N개의 정수가 주어진다. (20 ​≤ $t_{i}$ ≤ 215, $t_{i}$ = 2k (0 ≤ k ≤ 15, k는 정수))

 

출력

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

 

예제 입력1

5 2
1 4 4 8 1

예제 출력1

9

 

코드

참고

import sys
import heapq
 
n, m = map(int, input().split())
ph = list(map(int, input().split()))
ph.sort(reverse=True)
heap = []
 
for i in ph:
    if len(heap) < m:
        heapq.heappush(heap, i) # 큰 수부터 차례로 heap에 넣음
    else:
        tmp = heapq.heappop(heap) # 가장 작은 원소 삭제
        heapq.heappush(heap, tmp + i)
 
print(max(heap))

1. 입력을 받는다.

2. 전자기기의 충전 시간을 받은 리스트 ph를 내림차순 정렬한다.

3. heap에 충전 시간이 큰 것부터 차례로 넣는다.

4. 충전기의 개수만큼 heap이 차면, heap에서 제일 작은 수를 pop한다.

5. pop으로 빠져나온 충전 시간 tmp에 현재 충전하려는 기기의 충전 시간 i를 더해 다시 heap에 넣어준다.

6. 이렇게 모든 충전 기기에 대해 for문을 돌리면 끝!

 

 

 

#review

heap모듈을 잘 사용하지 않아 어려웠다. 익숙하도록 자주 사용하려고 노력해야겠다.