[BOJ 11399] ATM 파이썬(Python) 풀이

 

11399번: ATM

문제해설

전형적인 그리디 알고리즘 문제입니다.

그리디 알고리즘은 쉽게 말해서, 미래를 고려하지 않고 현 시점에서 최선의 선택을 하는 알고리즘을 말합니다.

 

정답 코드

 

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

times_list.sort()

sum = 0
cnt = 0
for t in times_list:
    cnt += t
    sum += cnt
print(sum)

 

예제로 주어진 [3, 1, 4, 3, 2]를 오름차순으로 정렬하여 [1, 2, 3, 3, 4]의 순서로 만들어줍니다.

이 순서대로 돈을 인출한다면 기다리는 시간을 최소화할 수 있게되어 최선의 선택이 됩니다.

시간복잡도는 sort과정에서 O(NlogN)이 되겠네요.

Python에서 list construction의 시간 복잡도는 O(len(...))입니다.

 

참고 : Python 시간복잡도 정리