BOJ 11399. ATM (Python)

문제

BOJ 11399

 

내가 생각한 풀이

사람의 수와 각 사람이 돈을 인출하는데 걸리는 시간 P_i가 주어질 때, 모든 사람이 돈을 인출하는데 필요한 시간의 최솟값을 출력하는 문제.

 

사람이 줄을 서는 순서에 따라 돈을 인출하는 시간이 달라지게 된다.

인출하는 시간이 짧은 사람부터 인출하는게 유리하다. Why? 앞 사람이 인출하는 시간이 뒷 사람들에게 전부 적용되기 때문

 

즉, 인출하는 시간을 담은 수열 P를 정렬한 후 앞의 값을 뒷의 값에 더해주고 sum함수 실행.

시간복잡도: O(N log N) + O(N-1) == O(N log N)

 

코드 (Python)

import sys
input = sys.stdin.readline

N = int(input().strip())
P = list(map(int, input().split()))
P.sort()
for i in range(N-1):
    P[i+1] += P[i]
print(sum(P))