[Python] 백준 11399번 ATM (실버4)

문제

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

사람들이 줄을 서는 순서에 따라서, 돈을 인출하는데 필요한 시간의 합이 달라지게 된다. 예를 들어, 총 5명이 있고, P1 = 3, P2 = 1, P3 = 4, P4 = 3, P5 = 2 인 경우를 생각해보자. [1, 2, 3, 4, 5] 순서로 줄을 선다면, 1번 사람은 3분만에 돈을 뽑을 수 있다. 2번 사람은 1번 사람이 돈을 뽑을 때 까지 기다려야 하기 때문에, 3+1 = 4분이 걸리게 된다. 3번 사람은 1번, 2번 사람이 돈을 뽑을 때까지 기다려야 하기 때문에, 총 3+1+4 = 8분이 필요하게 된다. 4번 사람은 3+1+4+3 = 11분, 5번 사람은 3+1+4+3+2 = 13분이 걸리게 된다. 이 경우에 각 사람이 돈을 인출하는데 필요한 시간의 합은 3+4+8+11+13 = 39분이 된다.

줄을 [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)

출력

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

예제 입력 1

5
3 1 4 3 2

예제 출력 1

32

---

풀이

문제의 조건을 만족시키는 최솟값을 도출하기 위해 수학적 사고력이 동원됩니다.

Point

• 수학

---

소스코드

n = int(input())

l = list(map(int,input().split()))
l.sort()

s = 0
for i in range(n):
    s += l[i]*(n-i)
print(s)

 

모든 사람이 돈을 뽑는데 걸리는 시간의 합의 최솟값을 구해봅시다.

첫번째 사람이 인출하는 데에 걸리는 시간은 뒤의 모든 사람들에게 영향을 줍니다.

 

첫번째 사람은 가장 빨리 돈을 뽑아야 모든 사람이 더 빨리 돈을 인출할 수 있습니다.

 

따라서 인출시간 오름차순으로 인출을 해야 합니다.

Line 1~4

n = int(input())

l = list(map(int,input().split()))
l.sort()

 

첫 input()은 ATM 줄에 선 사람의 수 입니다.

 

ATM에 선 사람의 인출 소요 시간을 list l로 받아줍시다.

 

인출 시간 합이 최소가 되기 위해서는 인출 시간이 빠른 순으로 앞에서부터 서야 합니다.

l.sort()로 정렬해줍시다.

Line 6~9

s = 0
for i in range(n):
    s += l[i]*(n-i)
print(s)

 

s에는 인출 시간의 합을 순차적으로 더해줄 겁니다. 0으로 초기화 해 줍시다.

 

list l의 i번째의 사람은 뒤의 모든 사람(n-i명)의 인출 소요 시간에 영향을 끼칩니다.

따라서 i번째 사람이 총 소요시간에 기여하는 시간은 l[i] * (n-i) 가 될 겁니다.

모든 i에 대해 적용시켜주면, s는 소요시간의 총 합이 나옵니다.