Python으로 푸는 백준 11399. ATM

백준 11399.ATM

 문제에서 하나의 ATM기를 이용하기 위해 줄서 있는 사람들이

각 사람이 돈을 인출하는데 기다리는 시간의 합이 최소가 되도록 하려고 한다.

어떻게 코드를 짜야 효율적으로 총 대기 시간을 구할 수 있을까.

문제 보러 가기

github에서 코드 보기

문제에서 제시한 조건

1. ATM기는 하나, N명의 사람들이 줄을 서 있다.

2. 각각의 사람이 현금을 인출하는데 걸리는 대기 시간은 앞 사람들의 처리 시간과 본인의 처리 시간을 더한 시간이다.

2. 모든 사람이 인출하는데 끝나는 시간이 아니라 각각의 사람이 인출하기 위해 대기한 시간의 총 합을 구하는 것이다.

문제 풀이 방법

- 뒷 사람이 조금이라도 덜 기다리고 돈을 인출하기 위해서는 가장 짧은 시간 동안 이용 가능한 사람들이 먼저 ATM기를 이용해야 한다.

- 따라서 가장 적은 시간만큼 이용하는 사람 순으로 정렬한 다음 각각의 대기 시간(waiting time)을 구하고 모든 대기시간을 더해 총 대기 시간(total time)을 구한다

수도 코드

sort time table

for time in time table:

waiting_time += time

total_time += waiting_time

return total_time

파이썬 코드

import sys
 
def greedy(line):
    total_time = 0
    waiting_time = 0
    line.sort()
    for time in line:
        waiting_time += time
        total_time += waiting_time
    return total_time
 
 
if __name__ == "__main__":
    n = int(sys.stdin.readline())
    line = list(map(int, sys.stdin.readline().strip().split()))
    print(greedy(line))
 

#백준 11399. ATM #python 백준 11399. ATM #백준 11399. ATM python #python 백준 11399. ATM #백준 11399. ATM python #11399 atm #백준 11399 atm #파이썬 11399 atm #11399 atm python #백준 11399 atm python #백준 atm #백준 greedy 알고리즘 문제