[백준] [python] 11399

Jinho Lee ·2023년 8월 8일

11399 ATM

시간제한: 1초

문제

인하은행에는 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)

출력

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

예제 입력1

5
3 1 4 3 2

예제 출력1

풀이 과정

문제 해석

각 사람들이 현금을 인출하는데 걸리는 시간의 합의 최소값을 구하는 문제.

사고 흐름

어떤 사람의 인출 시간을 구하기 위해서는 그 사람의 인출시간과 앞 사람들의 인출 시간의 합을 구해야 한다.
앞에 있는 사람이 인출하는 시간동안 뒷 사람들의 인출 시간이 모두 늘어나기 때문에 인출 시간이 짧은 사람을 앞에 배치하는 것이 유리하다.(인출 시간의 합을 최소로 만든다.)
매번 저장해놨던 앞사람들의 시간을 각각 더하는 것은 비효율적이다.
반복문을 사용해 이전 사람의 인출 시간을 갱신하며 현재 순회하고 있는 사람의 인출 시간과 더해준 값을 time_sum에 더해나간다면 코드를 간소화 할 수 있을 것이다.

코드 작성

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

# 인출하는데 걸리는 시간을 오름차순으로 정렬
time_arr.sort()

# 걸리는 시간의 합(결과값)
time_sum = 0

# 이전 사람이 인출하는데 걸리는 시간
time_before = 0

# 각 사람을 순회하며 걸리는 시간과 그 합을 구하기
for i in time_arr:
    
    # 이전 사람의 인출 시간 + 현재 방문한 사람의 인출 시간
    time_sum += time_before + i

    # 이전 사람의 인출 시간을 현재 사람의 인출 시간으로 갱신
    time_before += i

print(time_sum)

위의 방법은 배열의 각 항목을 순회할 때(각 사람을 순회할 때) 이전사람의 인출 시간과 현재 방문한 사람의 인출 시간만 접근하면 된다. 따라서 $O(N)$ 의 시간복잡도를 가진다.

시간을 더하는 과정에서 배열에 저장되어 있는 시간을 하나씩 다 더하는 방법도 있다.
반복문을 다음과 같이 바꾸어주면 된다.

for x in range(1, N+1):
    time_sum += sum(time_arr[0:x])

하지만 이 경우에는 배열의 각 항목을 순회할 때 sum() 함수를 사용하는데 sum() 함수의 경우 $O(N)$ 의 시간복잡도를 가지므로 전체 for문의 시간 복잡도는 $O(N^2)$ 이 된다. $(1 + 2 +$ $\dots$ $+ n-1 + n =$ $\frac{n(n+1)}{2}$ $)$
따라서 이전 방법보다 가독성은 좋지만 성능이 떨어진다.