11399.py

# ATM
# 시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
# 1 초	256 MB	129308	89328	70610	69.441%


# 문제
# 인하은행에는 ATM이 1대밖에 없다. 지금 이 ATM앞에 N명의 사람들이 줄을 서있다. 
# 사람은 1번부터 N번까지 번호가 매겨져 있으며, i번 사람이 돈을 인출하는데 걸리는 시간은 Pi분이다.

# 사람들이 줄을 서는 순서에 따라서, 돈을 인출하는데 필요한 시간의 합이 달라지게 된다. 
# 예를 들어, 총 5명이 있고, P1 = 3, P2 = 1, P3 = 4, P4 = 3, P5 = 2 인 경우를 생각해보자. 
# [1, 2, 3, 4, 5] 순서로 줄을 선다면, 1번 사람은 3분만에 돈을 뽑을 수 있다. 
# 2번 사람은 1번 사람이 돈을 뽑을 때 까지 기다려야 하기 때문에, 3+1 = 4분이 걸리게 된다. 
# 3번 사람은 1번, 2번 사람이 돈을 뽑을 때까지 기다려야 하기 때문에, 총 3+1+4 = 8분이 필요하게 된다. 
# 4번 사람은 3+1+4+3 = 11분, 5번 사람은 3+1+4+3+2 = 13분이 걸리게 된다. 
# 이 경우에 각 사람이 돈을 인출하는데 필요한 시간의 합은 3+4+8+11+13 = 39분이 된다.


# 줄을 [2, 5, 1, 4, 3] 순서로 줄을 서면, 
# 2번 사람은 1분만에, 5번 사람은 1+2 = 3분, 
# 1번 사람은 1+2+3 = 6분, 
# 4번 사람은 1+2+3+3 = 9분, 
# 3번 사람은 1+2+3+3+4 = 13분이 걸리게 된다. 
# 각 사람이 돈을 인출하는데 필요한 시간의 합은 1+3+6+9+13 = 32분이다. 
# 이 방법보다 더 필요한 시간의 합을 최소로 만들 수는 없다.

# 줄을 서 있는 사람의 수 N과 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어졌을 때, 
# 각 사람이 돈을 인출하는데 필요한 시간의 합의 최솟값을 구하는 프로그램을 작성하시오.

# 입력
# 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 
# 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000)

# 출력
# 첫째 줄에 각 사람이 돈을 인출하는데 필요한 시간의 합의 최솟값을 출력한다.


# My code: 누적합 리스트 이용
import sys
input = sys.stdin.readline
n = int(input())
drawList = list(map(int, input().split()))
sumList = [0] * n

drawList.sort()

for i in range(n):
    if i == 0:
        sumList[0] = drawList[0]
    else:
        sumList[i] = sumList[i-1] + drawList[i]
        
print(sum(sumList))


# 슈도코드 작성
# n 사람 수 
# A 자릿수별로 구분해 저장한 리스트
# S 누적합 리스트

# for i in range(1, N)
#     for j를 i-1 ~ 0까지 뒤에서 반복:
#         현재 범위에서 삽입될 위치 찾기
#     for j를 i ~ insert_point + 1까지 뒤에서 반복:
#         삽입하기 위해 삽입 위치에서 i까지 데이터를 한 칸씩 뒤로 밀기
#     삽입 위치에 현재 데이터 저장

# for i in range(1, N):
#     삽입을 위해 삽입 위치에서 i까지 데이터를 한 칸씩 뒤로 밀기
# 삽입 위치에 현 데이터 저장

# for i in range(1, N):
#     A 리스트를 이용해 S에 요소 채우기

# S 리스트의 요소를 모두 합한 값 출력


# Solution Code
# ATM기를 빨리 인출하는 방법을 풀기 위해 그리디 방식을 채택했다.
# 즉, 인출 시간이 가장 빠른 사람부터 인출하도록 순서를 정렬하는 것이 그리디 방식이다.
# 여기서 N =1000이고, 시간 제한이 1초이므로 시간 복잡도가 O(N^2) 이하인 알고리즘을 사용하면 된다.
n = int(input())    # 사람 수
A = list(map(int, input(). split()))    # drawList
S = [0]*n   # sumList

for i in range(1, n):
    # 삽입할 데이터 선택
    insertPoint = i
    insertValue = A[i]
    
    # ex. A = [3, 1, 4, 2]
    # 1) i=1, A[1] = 1을 index=0인 3에 삽입하려고 함.
    # 3>1 이므로 왼쪽으로 이동, 이때 j=0이므로 insertPoint = 0

    # 2) i=3, A[3] = 2인 경우
    # A[3]=2를 왼쪽에서([1, 3, 4]) 적절하게 삽입하려고 함.
    # j=2, A[2] = 4이고 4>2 이므로 왼쪽으로 이동
    # j=1, A[1] = 3이고 3>2 이므로 왼쪽으로 이동
    # j=0, A[0] = 1이고 1<2 이므로 멈춤, insertPoint = j+1 = 1로 설정
    # 따라서 insertPoint = 1이고 A[3]은 1번째 위치에 삽입됨.

    # j가 i-1 부터 -1(마지막 원소)까지 거꾸로 순회
    for j in range(i-1, -1, -1):    # 현재 데이터의 앞쪽을 탐색
        if A[j] < A[i]:             # 삽입 정렬이 일어나는 순간
            insertPoint = j + 1
            break
        if j == 0:                  # 리스트 맨 앞까지 왔으면 맨 앞에 삽입
            insertPoint = 0


    # i ~ insertPoint까지 뒤로 이동하며 요소들을 한 칸씩 밀음(오른쪽으로 이동, 인덱스 +1 증가)
    # 삽입 정렬을 하기 위해 자리를 마련하는 과정
    for j in range(i, insertPoint, -1): # 기존 원소들을 한 칸씩 오른쪽으로 이동
        A[j] = A[j-1]               
    A[insertPoint] = insertValue
    
    # ex. A = [3, 1, 4, 2], i=1인 경우
    # 1) insertPoint = 0, A[1]을 앞으로 이동
    # 2) A = [1] = 3이므로 [3, 3, 4, 2]
    # A[0] = 1 업데이트

S[0] = A[0]

for i in range(1,n):
    S[i] = S[i-1] + A[i]
    
sumValue = 0

for i in range(0, n):
    sumValue += S[i]
    
print(sumValue)