[백준 11399] ATM 해설 및 풀이 (파이썬)

백준 알고리즘 11399번 | ATM

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

---

문제

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

사람들이 줄을 서는 순서에 따라서, 돈을 인출하는데 필요한 시간의 합이 달라지게 된다. 예를 들어, 총 5명이 있고, P₁ = 3, P₂ = 1, P₃ = 4, P₄ = 3, P₅ = 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과 각 사람이 돈을 인출하는데 걸리는 시간 P_i가 주어졌을 때, 각 사람이 돈을 인출하는데 필요한 시간의 합의 최솟값을 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다.

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

 

출력

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

 

 

예제 입력 1

5
3 1 4 3 2

 

예제 출력 1

32

---

해설

이 문제가 요구하는 것은 각 사람이 돈을 인출하는데 필요한 시간의 합의 최솟값입니다.

"각 손님의 대기 시간의 총합을 최대한 줄이는 것"이 정답이겠네요.

 

예제 1번으로 해설해보겠습니다.

먼저 첫줄을 보면 손님은 5명이네요.

그 후 두번째 줄을 읽어보면 각 손님의 돈을 뽑는데 걸리는 시간은 다음과 같습니다.

• 3분
• 1분
• 4분
• 3분
• 2분

 

지금 들어온 순서대로 돈을 뽑는다면, 모두가 기다려야 하는 시간은 다음과 같습니다.

• 3 : 3분
• 3+1 : 4분
• 3+1+4 : 8분
• 3+1+4+3 : 11분
• 3+1+4+3+2 : 13분

모두가 돈을 인출하는데 걸리는 시간의 합은 3+4+8+11+13= 39분입니다.

 

 

모두가 돈을 인출하는데 걸리는 시간의 합을 최소한으로 줄이는 방법은 다음과 같습니다.

인출 시간이 적은 순으로 정렬하는 것입니다.

이런식으로요.

• 1분
• 2분
• 3분
• 3분
• 4분

 

이렇게 정렬하면 모두가 기다려야 하는 시간은 다음과 같습니다.

• 1 : 1분
• 1+2 : 3분
• 1+2+3 : 6분
• 1+2+3+3 : 9분
• 1+2+3+3+4 : 13분

모두가 돈을 인출하는데 걸리는 시간의 합은 1+3+6+9+13 = 32분입니다.

이보다 시간을 단축할 수 있는 방법은 없습니다.

---

다음은 해당 문제를 푸는 코드입니다.

n = int(input())  # 첫째줄 입력
peoples = list(map(int, input().split()))  # 기다리는 사람들 리스트 형태로 입력 받음

peoples.sort()  # 작은 순서대로 정렬
answer = 0  # 정답 변수를 0으로 만듭니다.

for x in range(1, n+1):
    answer += sum(peoples[0:x])  # 리스트의 0번째 수부터 x번째 수까지를 더해줍니다.
print(answer)  # 정답 제출