[Python] 23843번 콘센트

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

23843번: 콘센트

---

 

23/09/09

 

 

그리디적으로 생각하면 쉽게 풀 수 있는 문제다.

---

 

문제 접근 방식:

 

 

먼저 첫 번째 예제부터 살펴보자.

 

첫번째 예제는 $N = 5, M = 2$로 주어져 있고, $1 \ 4 \ 4 \ 8 \ 1$로 각 기기 별 충전 시간이 주어져 있다.

 

최소 시간은 $9$이다.

 

가장 오래 걸리는 $8$시간 짜리 기기를 첫 번째 콘센트에 꽂아 놓은 상태에서 $4$시간 짜리 기기 2개를 두 번째 콘센트를 통해 충전하면 $8$시간을 소요하여 3개의 기기를 충전할 수 있다.

 

이후 첫 번째 콘센트와 두 번째 콘센트에 각각 $1$시간 짜리 기기를 충전하면 총 $8+1 = 9$시간을 소모하여 모든 기기를 충전할 수 있다.

 

여기서 사용된 그리디적인 접근을 생각해 보면, "가장 오래 걸리는 기기"를 한쪽 콘센트에 꽂아 놓고 "동시에" 다른 기기들을 충전하는 방식이다.

 

 

기기가 충전이 오래 걸리는 순으로 $T_1, T_2, ...$와 같이 정렬돼 있다고 해보자.($T_1$이 제일 오래 걸린다.)

 

만약 콘센트가 $3$개라면, 우리는 $T_1$을 먼저 첫 번째 콘센트에 꽂아 놓고 두 번째 콘센트에 $T_2$를 꽂아 두면 된다.

 

만약 $T_2$가 $T_1$보다 더 작다면, 우리는 $T_2$가 끝나고 다른 기기를 꽃을 수 있으므로, (왜냐하면 걸리는 모든 시간은 $2$의 거듭제곱수이기 때문에 다른 기기를 꽃아 둘 수 있다는 것이 보장된다) $T_3$를 두 번째 콘센트에 꽃는다고 생각하면 된다.

 

만약 $T_3$까지 두 번째 콘센트에서 충전을 했는데도 첫 번째 콘센트에 충전이 안 끝났다면, 즉, $T_1 > T_2 + T_3$라면 $T_4$를 꽃을 수 있는지 살펴본다.

 

이를 반복하다가 만약 두번째 콘센트에서 충전하는 총시간이 첫 번째 콘센트에서 충전하는 콘센트의 총시간보다 길어지게 된다면, 그 기기를 세 번째 콘센트에 충전하도록 넘기면 된다.

 

그러다가 더 이상 모든 콘센트가 가득 차서 기기를 충전할 수 없다면, 모든 기기를 다 빼고 남은 기기부터 첫 번째 콘센트에 다시 꽃아야 한다.

 

이렇게 "동시에" 콘센트를 꽂아 놓고 쓰는 사이클은 첫 번째 콘센트에 꽂아 놓은 시간만큼 시간이 걸리므로, 그 시간을 전체 걸린 시간에 더해주면 된다.

 

이를 모든 기기가 충전될 때까지 반복해서 구현하면 된다. 

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더 보기를 누르면 확인할 수 있다.

# 23843번 콘센트
# 그리디, 정렬
import sys
input = sys.stdin.readline

N, M = map(int, input().rstrip().split())
T = sorted(map(int, input().rstrip().split()))
time_li = []
if M == 1:
    print(sum(T))
else:
    total_time = 0
    time = T.pop()
    time_li.append(time)
    while T:
        time = T.pop()
        if time_li[0] < time_li[-1] + time:
            time_li.append(time)
        else:
            time_li[-1] += time
        if len(time_li) > M:
            total_time += time_li[0]
            time_li = [time_li[-1]]
    total_time += time_li[0]
    print(total_time)