BOJ 11399번 : ATM (Python/Silver 4)

11399번: ATM

문제

인하은행에는 ATM이 1대밖에 없다. 지금 이 ATM앞에 N명의 사람들이 줄을 서있다. 사람은 1번부터 N번까지 번호가 매겨져 있으며, i번 사람이 돈을 인출하는데 걸리는 시간은 Pi분이다.

줄을 [2, 5, 1, 4, 3] 순서로 줄을 서면, 2번 사람은 1분만에, 5번 사람은 1+2 = 3분, 1번 사람은 1+2+3 = 6분, 4번 사람은 1+2+3+3 = 9분, 3번 사람은 1+2+3+3+4 = 13분이 걸리게 된다. 각 사람이 돈을 인출하는데 필요한 시간의 합은 1+3+6+9+13 = 32분이다. 이 방법보다 더 필요한 시간의 합을 최소로 만들 수는 없다.

줄을 서 있는 사람의 수 N과 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어졌을 때, 각 사람이 돈을 인출하는데 필요한 시간의 합의 최솟값을 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000)

 

출력

첫째 줄에 각 사람이 돈을 인출하는데 필요한 시간의 합의 최솟값을 출력한다.

---

예제 입력

5
3 1 4 3 2

예제 출력

32

---

풀이

기다리는 시간을 최소로 하기 위해서는 필요한 시간이 적은 순대로 정렬해야 한다.

1. 1 = 1
2. 1 + 2 = 3
3. 1 + 2 + 3 = 6
4. 1 + 2 + 3 + 3 = 9
5. 1 + 2 + 3 + 3 + 4 = 13

결과 : 1 + 3 + 6 + 9 + 13 (기다린 시간을 총 합해서 계산)

Solution

N = int(input())
P = list(map(int, input().split()))
P.sort()
r = 0
l = []
for i in P:
    r += i
    l.append(r)
print(sum(l))

Another Solution

N = int(input())
P = list(map(int, input().split()))
P.sort()
r = 0
for i in range(1, N+1):
    r += sum(P[0:i])
print(r)