문제 출처 : https://www.acmicpc.net/problem/11399

문제 파악

문제가 길지만 요하는 것은 간단하다.
사람의 수 N 이 주어지고, 각 사람이 돈을 뽑는데 걸리는 시간 P1,P2..Pn 이 주어졌을 때, 모든 사람들이 다 돈을 뽑았을 때, 각자 걸리는 시간의 합의 최솟값을 구하는 문제이다.

해결 아이디어

간단히 생각해보자.
어떤 일을 끝내는데 1시간걸리는 사람과, 100시간 걸리는 사람이 있다면

만약 100시간 걸리는 사람이 먼저 일에 들어간다면 1시간 걸리는 사람은 자기 차례가 될때까지 100시간을 기다려야 하지만,

1시간 걸리는 사람이 먼저 일에 착수한다면 100시간 걸리는 사람은 1시간만 기다리면 된다.

조삼모사 아닌가? 싶지만 아니다.

첫번째의 경우 각 사람이 소요되는 총 시간
1시간 걸리는 사람 : 100 + 1
100시간 걸리는 사람 : 100

• 총 201 시간

두번째 경우 각 사람이 소요되는 총 시간
1시간 걸리는 사람 : 1
100시간 걸리는 사람 : 1 + 100

• 총 102 시간

그러니 이 문제도 작업시간이 빠른 사람 먼저 작업에 들어가면 된다.

해답 및 풀이

import sys
input = sys.stdin.readline

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

time.sort() # 오름차순 정렬

total = 0 # 전체 합
cur = 0 # 현재 누적 합

for t in time:
    cur += t
    total += cur

print(total)