[ 백준 ] 11399번 : ATM (파이썬)

문제 )

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

11399번: ATM

 

[ 풀이 ]

✔ Greedy Algorithm을 사용하여 풀어준다. 

 

< Greedy Algorithm이란? > 

결정을 해 야 할 때마다 그 순간에 가장 좋다고 생각되는 것을 solution으로 선택함으로써  
최종 solution에 도달하는 Algorithm이다. 

 

각 사람이 돈을 인출하는데 필요한 시간의 합의 최솟값을 구하기 위해서는 돈을 인출하는 데 걸리는 시간인 P(i) 가 작은 순서대로 돈을 뽑아야한다. 


그러므로, P(i)의 list를 오름차순으로 정렬한 순서대로 돈을 뽑으면  돈을 인출하는데 시간의 합의 최솟값을 구할 수 있다. 

 

< Totaltime Function의 Algorithm >

✔ P(i)의 list  → arr
✔ 돈 인출하는 데 걸리는 시간의 총 합 → total
✔ 1사람이 돈을 인출하는 데 걸리는 시간 → person

1. arr을 오름차순으로 정렬한다
2. arr의 원소에 하나씩 접근한다 → i
            Ⅰ.  i번째 사람이 돈을 인출하는 데 걸리는 시간(person)을 구한다
            Ⅱ.  i번째 사람까지의 걸리는 시간의 합(total)을 구한다. 

 

 

- python code

import sys
input=sys.stdin.readline

def Totaltime(arr):
    arr.sort() # 오름차순으로 정렬
    total=0 #  i번째 사람까지의 걸리는 시간의 합(total)
    person=0 #  i번째 사람이 돈을 인출하는 데 걸리는 시간
    for i in arr:
        person+=i
        total+=person
    return total

N= int(input())
p=list(map(int,input().split()))
print(Totaltime(p))