백준 23843번 - 콘센트

콘센트 문제 바로 가기

풀이 날짜: 2026-03-09

baekjoon 알고리즘 문제 풀이

풀이 코드

import sys
input = sys.stdin.readline
import heapq

n,m = map(int, input().split())
data = list(map(int, input().split()))
data.sort(reverse=True)
heap = []

for i in range(min(m,n)):
    heapq.heappush(heap, data[i])

for i in range(m,n):
    a = heapq.heappop(heap)
    new = a + data[i]
    heapq.heappush(heap, new)

print(max(heap))
  

문제 핵심 요약:

여러 개의 전자기기를 제한된 수의 멀티탭에 연결하여 충전할 때, 모든 충전이 완료되는 최소 시간을 구하는 문제이다. 따라서 전자기기를 어떤 순서로 충전기에 배치해야 전체 충전이 끝나는 시간을 최소화할 수 있는지 계산하는 것이 핵심이다.

접근 방법

이 문제는 여러 작업을 동시에 처리할 때 가장 빨리 끝나는 작업을 기준으로 다음 작업을 배치하는 스케줄링 문제로 볼 수 있다. 충전기가 여러 개 존재하기 때문에 각각의 충전기가 언제 비는지를 관리해야 하는데, 이때 가장 빨리 끝나는 충전기를 빠르게 찾을 수 있는 자료구조가 필요했다. 파이썬에서는 heapq를 사용하면 가장 작은 값(가장 빨리 끝나는 시간)을 효율적으로 꺼낼 수 있으므로, 각 충전기의 현재 충전 완료 시간을 힙(Heap)에 저장하여 관리하였다.

풀이 전략

먼저 충전 시간이 긴 전자기기부터 처리하는 것이 전체 시간을 최소화하는 데 유리하기 때문에, 전자기기의 충전 시간을 내림차순으로 정렬하였다. 그 다음 처음 m개의 전자기기를 각각의 충전기에 바로 연결하고, 이후 남은 전자기기들은 다음과 같은 과정을 반복했다.

1. 힙에서 가장 빨리 끝나는 충전기를 꺼낸다.
2. 해당 충전기에 다음 전자기기의 충전 시간을 더한다.
3. 새롭게 계산된 충전 완료 시간을 다시 힙에 넣는다.

이 과정을 모든 전자기기가 배치될 때까지 반복하면, 힙에는 각 충전기의 최종 충전 완료 시간이 저장된다. 이 중 가장 큰 값이 전체 충전이 끝나는 최소 시간이 된다.