[골드 5] 백준 23843 - 콘센트 (파이썬)

https://www.acmicpc.net/problem/23843

풀이

• 총 N개의 기기를 충전해야 한다.
• 충전기는 M개의 콘센트가 있다.
• 각 기기를 충전하는 데 걸리는 시간이 배열 A로 주어진다.
• 한 번에 M개까지 충전 가능하며, 각 콘센트는 병렬로 작동한다.
• 모든 기기를 충전 완료하는 데 걸리는 최소 시간을 구하라.

A.sort(reverse=True)  # 시간이 긴 기기부터 우선 배정

• 가장 긴 기기부터 먼저 처리해야 전체 시간이 줄어든다.
• 그리디 전략: 긴 작업을 먼저 분산시켜야 부하가 치우치지 않음.

pq = [0] * M
heapq.heapify(pq)

• pq: 각 콘센트의 누적 충전 시간을 관리
• 처음엔 모두 0초 (아무것도 안 꽂힌 상태)
• heapq를 사용해서 가장 빨리 끝나는 콘센트를 찾기 용이하게 함 (최소 힙)

for t in A:
    min_val = heapq.heappop(pq)
    heapq.heappush(pq, min_val + t)

• 충전 시간이 가장 짧은 콘센트를 골라서 기기 t를 할당
• 이 기기의 충전 시간 t만큼 누적하여 다시 힙에 넣음
• => 이 과정을 통해 부하를 최대한 균등하게 분산

코드

# 백준 23843 - 콘센트
# 분류 : 그리디

N, M = map(int, input().split())
A = list(map(int, input().split()))

A.sort(reverse=True)

B = [0] * M
pos1 = 0
while True :
    B[0] += A[pos1]
    pos1 += 1

    pos2 = 1
    while pos1 < N and pos2 < M :
        B[pos2] += A[pos1]
        pos1 += 1

        if B[pos2] == B[0] :
            pos2 += 1

        if pos1 == N :
            break
print(B[0])