[백준] 11399번 ATM - Python / 알고리즘 중급 1/3 - 그리디 알고리즘

---

---

---

💡 문제

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

사람들이 줄을 서는 순서에 따라서, 돈을 인출하는데 필요한 시간의 합이 달라지게 된다. 예를 들어, 총 5명이 있고, P$_1$ = 3, P$_2$ = 1, P$_3$ = 4, P$_4$ = 3, P$_5$ = 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 ≤ P$_i$ ≤ 1,000)

출력

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

---

💭 접근

이 문제의 경우 각각의 사람이 돈을 인출하는데 필요한 시간의 합을 구하는 문제이다. 이 문제를 풀어서 써보면 아래와 같다.

예제 1 5, [3, 1, 4, 3, 2]
answer = 3 + (3 + 1) + (3 + 1 + 4) + (3 + 1 + 4 + 3) + (3 + 1 + 4 + 3 + 2)
=> (3 x 5) + (1 x 4) + (4 x 3) + (3 x 2) + (2 x 1)
=> 15 + 4 + 12 + 6 + 2 = 39

이와 같이 1번째 사람이 필요한 시간이 n번 더해지고, 2번째 사람은 n-1번, 3번째 사람은 n-2번 더해지게 된다. 따라서 시간의 합의 최소값을 구하기 위해선 큰 수를 최대한 적게 더해야 하므로 입력으로 주어진 시간을 내림차순으로 정렬한 후, 가장 큰 수부터 1~n까지 곱하며 더해주면 된다.

---

📒 코드

n = int(input())
time = list(map(int, input().split()))
time.sort(reverse=True)

ans = 0
for i in range(n):
    ans += time[i] * (i + 1)

print(ans)

---

💭 후기

간단한 그리디 알고리즘 문제였다.

---

🔗 문제 출처

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

---