BOJ #11399

Level :

silver3

문제 요약 :
총 주어진 인원이 atm을 이용했을 때 걸린 최소의 시간을 구하는 것.
N = 인원수
i = (0~N-1)

해결 방안 :

각 소요시간이 다른 N명의 인원들의 순서 배치가 관건이었다.

총 소요시간에 있어, Pi의 개별 소요시간은 Pi * (N-i) 만큼 기여를 한다.

그렇기에 개별 소요시간의 합을 최소화 할 수있는 방법은 오름차순으로 P_arr를 정렬하는 것이다. 여기서 greedy 개념이 들어간 것 같다.

오름차순 정렬 후 위에서 정리한 식으로 각 소요시간을 다 더해준면 총 소요시간의 최솟값을 구할 수 있다.

시간 복잡도 :

• 파이썬의 내장 함수인 sort()의 시간 복잡도 : NlogN (Timesort)
• 개별 Pi 소요시간으로 최소 sum을 구하기 위한 for 문 : N

= N(logN+1)

O(NlogN)

solution :

import sys
input = sys.stdin.readline
if __name__ == "__main__" :
    sum = 0
    n = int(input().strip())
    arr = list(map(int,input().strip().split()))
    arr.sort()
    for i in range(n) :
        sum += arr[i]*(n-i)
    print(sum)