백준 11399 ATM

11399번: ATM

첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000)

www.acmicpc.net

문제에 대해 조금 생각을 해보면 최종 시간의 합이 최소값이 되기 위해서는 가장 적은 시간을 할애하는 사람이 가장 먼저 ATM을 사용하는 것이 좋다 왜냐하면 대기 시간이 긴 사람의 경우 그 뒤의 사람들도 그 시간 만큼 대기를 해야하기 때문이다.

그래서 대기 줄을 sort()해서 최종 시간의 합을 생각하면 첫번째 사람의 대기 시간은 이후 마지막 사람의 대기 시간까지 더해지기에

[첫번째 대기 사람 시간] * [줄의 길이]

만큼 최종 대기 시간에 포함되어 있다 같은 논리로 두 번째 사람의 대기 시간을 생각하면

[두번째 대기 사람 시간] * [줄의 길이-1]

이 된다 이 논리로 알고리즘을 작성하면 다음과 같이 된다

N = int(input()) #ATM기 인원 입력

line = list(map(int, input().split(' ',N))) #줄 line에 N명 만큼만 list로 입력받기

line.sort() #오름차순 정렬

tot = 0 #결과를 tot로

for i in range(N):

tot = tot + line[i]*(N-i)

print(tot)

SOECP