[대회][BOJ][INU 코드페스티벌 2021] C번 23843 : 콘센트

문제를 정리해보자.

 

1. N개의 전자기기를 충전해야 한다.

2. M개의 사용 가능한 콘센트가 있다.

 

전자기기 1개당 콘센트 1개가 필요하다.

그리고 전자기기마다 충전에 필요한 시간, T가 주어진다.

 

모든 전자기기를 충전하기 위한 최소 시간을 구해야 한다.

 

 

풀이를 생각해보자.

 

이 문제는 '최소 대기시간으로 충전해서 가져가는 최대 인원'을 구하는 게 아니라,

'모든 기기를 충전하는 최소 시간'을 구하는 것이다.

 

 

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

 

문제의 예시로 전자와 후자를 비교해보자.

 

 

 

전자 vs 후자

 

 

전자는 13시간이 걸리고, 후자는 9시간이 걸린다.

따라서 충전이 오래 걸리는 기기부터 충전해야 한다.

 

정리해보면, 

넣을 때는 충전이 가장 오래 걸리는 기기를 넣는다.

그리고 콘센트 누적 충전 시간에 현재 기기 충전 시간을 더한다. (처음에는 0이다.)

그다음에, 콘센트 누적 충전이 가장 적은 콘센트에 다음 기기를 넣는다.

 

 

 

후자 수기로 풀이 작성

 

 

 

구현해보자.

 

 

n, m = map(int, input().split())  # 전자기기 수, 콘센트 수
li = list(map(int, input().split()))

li.sort(reverse=True)

box = li[:m]
li = li[m:]

for num in li:
    box.sort()
    box[0] += num

print(max(box))

 

 

시간 복잡도는 O(NlogN)이다.