[그리디] 백준 11399 ATM

 

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

11399번: ATM

 

문제 요약

입력

사람 수 N

각 사람 당 인출 시간 (Pi = i번 사람의 인출 시간)

출력

인출 시간 총합의 최소값

 

예시

총 5명

p1 = 3, p2 = 1, p3 = 4, p4 = 3, p5 =2

 

 

i = [1, 2, 3, 4, 5]  순으로 인출하면

 

각 사람당 인출 시간은 3 1 4 3 2 이므로, 대기 시간을 포함한 총 인출 시간은

3+(3+1)+(3+1+4)+(3+1+4+3) + (3+1+4+3+2)

= 3 +4 + 8 + 11 + 13 = 39 이다.

 

 

i = [2, 5, 1, 4, 3] 순으로 인출하면

 

각 사람당 인출시간은 1 2 3 3 4 이므로, 총 인출 시간은

1 + (1+2) + (1+2+3) + (1+2+3+3) + (1+2+3+3+4)

= 1 + 3 + 6 + 9 + 13 = 32 이다.

 

두 번째 경우가 총 인출 시간의 최소값이다.

 

 

풀이방법

인출시간이 적은 순으로 정렬해야 한다.

 

n과 P의 각 요소를 입력 받는다.

리스트 P를 정렬한다.

 

for i in range(P의 길이-1)

       P[0] ~ P[i]만큼 더한다.

 

 

제출 코드

import sys

n = int(input())
t = list(map(int,sys.stdin.readline().split()))

t.sort()

result = 0
for i in range(len(t)):
    for j in range(0,i+1):
        result+=t[j]

print(result)

 

한 줄에 여러 요소가 들어올 때 list(map(int, input().split()))을 사용한다.

input()을 sys.stdin.readline()으로 변경하면 빠르게 입력을 받을 수 있다.