[백준(BOJ)] 11399번 ATM - 파이썬/python

문제

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

11399번: ATM

ATM 앞에 줄을 서있는 사람의 수와 각 사람이 돈을 인출하는 데 걸리는 시간이 주어진다. 각 사람이 돈을 인출하는데 필요한 시간의 합의 최솟값을 구하는 문제다.

예시

Example 1:

Input: 5
    3 1 4 3 2
Output: 32

풀이

import sys
input = sys.stdin.readline

n = int(input())
time = list(map(int, input().split()))
time.sort()

ans = 0
for i in range(n):
    ans += sum(time[:i+1])

print(ans)

 

- 처음에 이 문제를 풀었을 때, 시간을 정렬하고 반복문 안에서 돈을 인출하는데 필요한 시간을 계속해서 더해줬다. 문제를 통과하긴 했지만, 매 반복마다 부분 리스트를 계산하므로 입력이 커지면 입력 크기에 따라 제곱 관계로 늘어나게 되어 계산 시간이 크게 증가할 수 있는 문제가 있다.

 

import sys
input = sys.stdin.readline

n = int(input())
time = list(map(int, input().split()))
time.sort()

ans = 0
sum_lst = []

for i in range(n):
    ans += time[i]
    sum_lst.append(ans)

print(sum(sum_lst))

 

- 시간 정렬을 똑같이 한 후에 누적 합을 활용하여 최종 값을 출력하는 방식으로 작성했다. 누적 합을 사용하여 각 시점에서의 누적 값을 더 효율적으로 얻을 수 있다.