[ BOJ 11399 ] ATM(Python)

문제

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))