[백준] 11399 ATM

🌭 문제 설명

• 인하은행에는 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)

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

---

😎 나의 풀이

from itertools import accumulate

N = int(input())  
P = list(map(int, input().split())) 

arr = sorted(P)  

result = list(accumulate(arr))  
print(sum(result)) 

1. 배열 P를 오름차순 정렬한다.
2. 파이썬의 accumulate라는 누적합 라이브러리를 사용해서 arr을 계산한다.
3. 누적합들을 더한 결과를 출력한다.

---

🧵 다른 풀이

N = int(input())
P = list(map(int, input().split()))

P = sorted(P)
waiting = [0] * N
waiting[0] = P[0]

for i in range(1, N):
  waiting[i] = waiting[i - 1] + P[i]

print(sum(waiting))

1. 그리디 알고리즘 방법으로 풀었다.
2. 배열 P를 정렬 시키고 , 대기시간 배열waiting을 초기화 하고 첫번째 값은 P의 값이기 때문에 해당 값으로 초기화
3. 두번째 값부터 마지막까지 대기시간을 구해준다.
4. waiting배열의 합을 출력한다.

---

• 그리디 를 적용해서 풀어보았다.