[백준 11399번] ATM

# ATM

n = int(input())
time_list = list(map(int,input().split()))

time_list.sort()

total = 0
solution = 0

for i in time_list:
    total = total + i
    solution += total

print(solution)

 

이번 문제는 각 사람들이 돈을 인출하는데 걸리는 시간의 합에 대한 최솟값을 구하는 문제였는데, 난이도는 상당히 쉬운 편에 속하여 3분도 되지 않아 풀 수 있었다. (그래서 정답률이 높은 ,,)

 

이 문제의 핵심은 인출하는데 걸리는 시간이 적게 걸리는 순서대로 돈을 인출하는 것이다. (Greedy 알고리즘)

왜냐하면 앞의 사람이 인출하는데 시간이 오래 걸릴수록 뒤에 있는 사람들은 그 시간만큼 기다려야 하기 때문이다.

 

따라서 뒤에 사람들이 기다리는 시간을 최소화하기 위해서는 빨리 인출할 수 있는 사람(소요 시간이 적은 사람)부터 인출하도록 하는 것이 맞다.

 

그래서 이 문제는 먼저 인출하는데 소요되는 시간이 적은 순서대로 정렬하고, 각 사람마다 인출하는데 소요되었던 시간을 total 변수에 저장한 뒤에 그 값을 solution 변수에 더해주었다.(모든 사람들이 소요된 시간의 합이기 때문에)