[백준][PYTHON] 11399번 ATM

문제

https://www.acmicpc.net/problem/11399

 

문제는 길지만, 요약하자면 각 사람이 돈을 인출하는데 필요한 시간의 합의 최솟값을 구하면 되는 것이다. 

 

풀이

import sys

# 문제 입력받기
N = int(input())
lines = list(map(int, sys.stdin.readline().split()))
lines.sort()

sum_list = [0]
# 누적합 구하기
for line in lines:
    tmp = line + sum_list[-1]
    sum_list.append(tmp)
    
print(sum(sum_list))

 

먼저, 인출 시간이 적은 사람 순으로 정렬을 한 후, 각 사람마다 걸리는 시간을 합한다. 

즉, 

입력이 3 1 4 3 2 로 주어질 때, 

1 2 3 3 4 순으로 정렬한 후, 

1 : 1분 소요

2 : 1+2=3분 소요

3 : 1+2+3=6분 소요

3 : 1+2+3+3=9분 소요

4 : 1+2+3+3+4=13분 소요

가 되며, 

모두 돈을 인출하는데 걸리는 시간의 합은 1+3+6+9+13=32분이 된다. 

 

 

다른 사람 풀이

좀 더 쉽게 누적합을 구한 풀이를 발견하여 함께 남겨본다. 

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

P.sort()

answer = 0
for i in range(1, N+1):
    answer += sum(P[:i])

print(answer)