Categories
Algorithm🧩
백준 📝
BookReview📕
CleanCode✨
Network 📨
Database 🗄
DevOps☁️
에러 일기📕
Etc💬
Fishy Fish 🎣
Spring🌱
[백준] 11399 ATM
백준 11399 ATM
문제
인하 은행에는 ATM이 1대 있고 이 앞에 N명의 사람이 줄 서있다.
사람은 1~N까지 있으며, i번째 사람이 돈을 인출하는데 걸리는 시간은 Pi분이다.
사람들이 줄을 서는 순서에 따라 돈을 인출하는데 필요한 시간의 합이 달라진다.
ex) p1 = 3, p2 = 1, p3 = 4, p4=3, p5 = 2
- 1번 사람: 3분
- 2번 사람: 3+1 = 4분
- 3번 사람: 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 순서로 서면 32분이 걸리고 이 값은 최소이다.
줄을 서있는 사람 수 N과 각 사람이 돈을 인출하는데 걸리는 시간 P가 주어졌을 때, 각 사람이 돈을 인출하는데 필요한 시간의 합의 최솟값을 구하는 프로그램을 작성하시오.
입력
- 첫째줄: 사람의 수 N
출력
첫번째 줄: 돈을 인출하는데 필요한 시간의 합의 최솟값
해결 방식
그리디 알고리즘 문제
- 앞에 위치한 사람의 인출 시간이 길어질 수록 대기 시간이 길어진다. → 인출 시간이 적은 사람부터 인출하도록 정렬한다.
코드
n = int(input())
p = list(map(int, input().split()))
p.sort() # 정렬
total = 0
# 대기 시간 계산
for i in range(1, n+1):
total += sum(p[0:i])
print(total)
