[백준 11399번] ATM

문제 개요

문제 링크 : https://www.acmicpc.net/problem/11399

 

 

위 문제를 쉽게 얘기하면

 

ATM 앞에 사람들이 줄을 서 있습니다.

각 사람은 돈을 인출하는데 걸리는 시간이 모두 다릅니다.

이제 줄을 어떻게 세울지를 우리가 정할 수 있습니다.

누가 먼저 인출할지 정해서, 

모든 사람이 기다리는 시간의 총합을 최소화 해야하는 문제입니다.

 

예를 들어 입력이

5
3 1 4 3 2

 

이렇게 들어왔으면

• 사람 수 : 5명
• 각 사람이 인출하는데 걸리는 시간 : [3, 1, 4, 3, 2]

이걸 직접 풀어보면 다음과 같습니다.

사람	인출시간	대기시간	누적합
1	3	0	0 + 3 = 3
2	1	3	3 + 1 = 4
3	4	4	4 + 4 = 8
4	3	8	8 + 3 = 11
5	2	11	11 + 2 = 13

 

총 대기 시간의 합은  3 + 4 + 8 + 11 + 13 = 39 가 나오게 됩니다.

 

이제 이걸 시간이 짧은 순으로 정렬 해보겠습니다.

사람	인출시간	대기시간	누적합
1	1	0	1
2	2	1	3
3	3	3	6
4	3	6	9
5	4	9	13

 

총 대기 시간의 합은  1 + 3 + 6 + 9 + 13 = 32  가 나오게 됩니다.

 

여기서의 중요한 포인트는 짧은 사람부터 진행해야 한다는 점입니다.

기다리는 시간이 누적되기 때문에, 앞에 서는 사람이 짧을수록 뒤에 사람들에게 영향을 덜 주게됩니다.

이게 바로 그리디 알고리즘의 핵심입니다.

 

코드

import sys

def solve():
    N = int(sys.stdin.readline())  # 사람 수
    times = list(map(int, sys.stdin.readline().split()))  # 각자의 인출 시간

    # 시간 짧은 순으로 정렬하면 전체 대기 시간이 최소가 됨
    times.sort()

    total = 0  # 최종 정답 (전체 대기 시간의 합)
    prefix_sum = 0  # 각 사람까지의 누적 대기 시간

    for time in times:
        prefix_sum += time
        total += prefix_sum

    print(total)

if __name__ == "__main__":
    solve()

 

`times.sort()` 를 한 이유는 짧게 걸리는 사람부터 정렬하면 뒤에 오는 사람들이 덜 기다리게 때문입니다.

 

그리디 알고리즘의 핵심은

지금 당장 "가장 적게 걸리는 선택"이 전체에 이득이 된다는 점입니다.

 

시간복잡도는 다음과 같습니다.

단계	시간
정렬	`O(N log N)`
누적합 계산	`O(N)`
전체	`O(N log N)` <충분히 빠름>