오픈하자마자 손님이 한꺼번에 몰렸다면?

동네 카페 '코드빈'에 오픈과 동시에 손님 5명이 들이닥쳐 동시에 주문했습니다. 바리스타는 한 번에 한 잔씩만 만들 수 있고, 각 음료의 조리시간은 제각각입니다.

조리시간(분): [3, 1, 4, 1, 5]

손님은 자기 음료가 나올 때까지 기다립니다. 그럼 누구 음료부터 만들어야 모든 손님이 기다린 시간의 합이 가장 작아질까요?

핵심은 "앞 주문일수록 여러 번 더해진다"

먼저 만든 주문 하나가 늦어지면, 그 뒤에서 기다리는 모든 손님이 함께 그만큼 더 기다립니다. 즉 맨 앞에 둔 주문의 조리시간은 한 번이 아니라 여러 번 총 대기시간에 더해지는 셈이에요.

조금 더 정확히 보면 — 조리시간 c인 주문을 앞에서 k번째에 두면, 그 c는 자기 손님 + 뒤에 남은 손님들이 전부 함께 견디므로 총합에 (N - k)번 더해집니다.

그러니 결론은 자연스럽습니다. 반복 횟수가 가장 많은 맨 앞자리에는, 가장 짧은 주문을 두자. 짧은 음료를 먼저 빼주면 그 뒤 손님들의 누적 대기가 최소로 억제됩니다.

직관은 알겠는데, *정말 항상* 최적일까요? 인접한 두 주문만 떼어놓고 생각해봅니다. 앞에 a, 바로 뒤에 b가 있다고 할 때, 이 둘의 순서만 바꿔도 다른 손님들의 대기는 전혀 변하지 않습니다. 바뀌는 건 이 두 주문 자신의 대기뿐이에요.

차이는 딱 a - b. 즉 a > b라면 b를 앞으로 보내는 게 무조건 이득입니다. 이 성질이 *모든* 인접쌍에서 성립하니, 더 이상 바꿔서 이득 볼 게 없는 상태 = 조리시간 오름차순이 최적이라는 결론에 도달합니다.

정리하면 풀이는 이렇게 짧아집니다.

1. 조리시간을 오름차순으로 정렬한다

2. 앞에서부터 더해가며 누적 조리시간(= 각 손님의 완료시각) 을 구한다

3. 완료시각을 전부 더하면 그게 최소 총 대기시간

[3,1,4,1,5]를 정렬하면 [1,1,3,4,5], 완료시각은 1, 2, 5, 9, 14 — 합은 31분입니다. (입력 순서 그대로 만들면 38분이라 더 손해예요.)

말로는 (N - k)번 더해진다는 게 와닿지 않을 수 있어요. 그런데 막대를 시간축에 이어 붙여 놓고 보면 완전히 다릅니다. 짧은 막대를 앞에 둘수록 뒤 막대들의 시작점이 왼쪽으로 당겨지고, 그만큼 완료시각의 합이 줄어드는 게 한눈에 보이거든요.

단계별 애니메이션으로 따라가면, "아, *이래서* 짧은 것부터구나"가 한 번에 이해됩니다.

이 패턴(정렬 후 누적합 그리디)은 "회의실 배정", "작업 스케줄링", "최소 평균 대기시간" 등 수많은 옷을 입고 코딩테스트에 등장합니다. 한 번 원리를 눈으로 익혀두면 어떤 변형이 나와도 흔들리지 않습니다.