[백준 온라인 저지] ATM

문제 출처

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

11399번: ATM

 

문제 해설

• 사람이 N명이고, 각 사람이 돈을 인출하는 데 걸리는 시간을 주어진다.
• ATM 기기가 하나밖에 없기 때문에 줄을 잘 배정하여 모든 사람이 돈을 인출하는 게 덜리는 시간의 합이 최소화하도록 하기
• 이 문제의 경우, 1번이 인출해야 2번이 인출이 가능하고 2번이 인출해야 3번이 인출이 가능하다.
  • 즉, n번째 사람이 인출하려면 n1, n2, .... , n-1번 사람이 모두 인출이 되어야 한다.
  • 이를 수식으로 변경하면 Tn = T1 + T2 + ... + Tn-1 (T는 인출 시간, n은 순서)
• 시간의 합이 최소가 되기 위해서는 앞선 사람의 인출하는 시간이 최소가 되어야 한다.
  • 3명이 인출하게 된다면 총 인출 시간은 (3T1 + 2T2 + T3)가 될 것이다.
  • 여기서 합계가 최소가 되려면 T1이 제일 작은 수가 되어야 한다.
• 따라서, 이 문제에서 돈을 인출하는데 걸리는 시간을 오름차순으로 정렬해서 합계를 구하면 문제는 해결될 것으로 예상

 

나의 풀이 (Python3)

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

import sys

N = int(sys.stdin.readline().strip())
P = list(map(int, sys.stdin.readline().strip().split()))

answer = 0

P = sorted(P)

for i in range(N):
    answer += sum(P[:i+1])
    
print(answer)