백준 11399번: ATM [python]

https://www.acmicpc.net/problem/11399

문제 접근

사람이 N명 있고, 각자 소요시간이 정해져있을 때
각각의 소요시간+대기시간 의 전체합이 가장 최소가 되게 하는 문제.

최소가 되려면 소요시간은 바꿀 수 없으니 대기하는 시간을 최소로 해야한다.

즉 소요시간이 적게 걸리는 사람부터 먼저 처리를 해주어야 한다.

해답 및 풀이

import sys

input = sys.stdin.readline

N = int(input())
time = list(map(int, input().split()))
time.sort()

total = 0       # 최종 정답
current = 0     # 지금까지의 누적합

for t in time:
    current += t      # 누적합 업데이트
    total += current  # 누적합을 total에 더함

print(total)

time[0] + (time[0] + time[1]) + (time[0] + time[1] + time[2]) + ... + (time[0] + ... + time[N-1])

누적합들의 총합을 구하는 로직을 for문으로 표현하기 어려웠다.