Search

[백준 11399] ATM

[백준 11399] ATM

Tip

i번 사람이 돈을 인출하는 데 걸리는 총 시간
1, 2, 3, ... i-1번째 사람까지 돈을 인출하는 걸 기다리는 시간 + i번 사람이 돈을 인출하는 데 걸리는 시간 Pᵢ
각각의 사람들이 돈을 인출하는 데 걸리는 시간의 총 합을 구해라!
1번째 사람 : P₁ 2번째 사람 : P₁ + P₂ 3번째 사람 : P₁ + P₂ + P₃ i번째 사람 : P₁ + P₂ + P₃ + ... + Pᵢ
더 앞에 서 있는 사람일수록 해당 사람의 인출 시간이 누적합에 많이 들어가게 됨!
최솟값을 구하기 위해선 인출 시간이 짧은 사람일수록 앞에 세워야 한다! → 그리디

풀이 소스 코드

import sys si = sys.stdin.readline n = int(si()) p = sorted(list(map(int, si().split()))) # 인출에 걸리는 시간을 오름차순 정렬 result = 0 # 각각의 사람들이 돈을 인출하는 데 걸리는 시간의 총합 for i in range(1, n + 1): for j in range(i): # 각각 사람의 바로 앞 사람의 인출시간을 누적해가며 result += p[j] print(result)
Python