소요 시간이 작은 순으로 ATM을 이용하는 경우가 소요 시간이 최소인 경우이다.
최소 소요시간을 만족하는 경우는 제일 마지막 사람이 기다리는 시간이 가장 작은 경우일 것이다. 이는 결국 오름차순으로 ATM을 사용하여야 한다는 것을 알 수 있다.
from sys import stdin
N = int(stdin.readline())
p = [int(i) for i in stdin.readline().split()]
p.sort(reverse=False)
mul = N
sum_ = 0
i = 0
while i < N and mul > 0:
sum_ += p[i] * mul
mul -= 1
i += 1
print(sum_)
위 아이디어를 바탕으로 정직하게 구현해 본 코드이다. 사람들을 소요 시간이 작은대로 정렬하고 가중치(p[i]
로 인해 추가되는 p[i+1:]
들의 대기시간을 의미)를 곱해 합을 구한다.
소요 시간이 많은 순으로 정렬하면 하나의 인덱스 변수만으로 해당 반복문의 논리를 구현할 수 있다.
from sys import stdin
N = int(stdin.readline())
p = [int(i) for i in stdin.readline().split()]
p.sort(reverse=True)
sum_ = 0
i = 0
while i < N:
sum_ += p[i] * (i + 1)
i += 1
print(sum_)