https://www.acmicpc.net/problem/11399
ATM기가 한 대밖에 없어서 줄을 서서 기다려야 한다.
이 때 각 사람은 인출하는데에 소요되는 시간이 다르다.
각 사람이 인출을 할 때까지 기다리는 시간의 합이 가장 짧도록 코드를 작성해보자.
인출 하는데에 소요되는 시간이 짧은 순으로 인출을 시키면
평균 대기 시간이 줄어든다.
humans = sorted(list(map(int,input().rsplit())))
# 시간이 짧은 순으로 정렬
dp[i] = i번째 사람이 인출을 할 때까지 기다리는 시간
dp = [0 for _ in range(n)]
dp[0] = humans[0]
# 앞 사람이 인출 하는데에 걸리는 시간을 더해준다.
for i in range(1,n):
dp[i] += dp[i-1] + humans[i]
나는 불필요한 dp 배열을 만들었지만
변수 하나를 선언해서 계속 더해주면 된다.
import sys
input = sys.stdin.readline
n = int(input())
humans = sorted(list(map(int,input().rsplit())))
dp = [0 for _ in range(n)]
dp[0] = humans[0]
for i in range(1,n):
dp[i] += dp[i-1] + humans[i]
print(sum(dp))