Your Name

I am an amazing person.

2 분 소요

문제 설명

백준 2839번 ATM

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

사람들이 줄을 서는 순서에 따라서, 돈을 인출하는데 필요한 시간의 합이 달라지게 된다. 예를 들어, 총 5명이 있고, $P_1$ = 3, $P_2$ = 1, $P_3$ = 4, $P_4$ = 3, $P_5$ = 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과 각 사람이 돈을 인출하는데 걸리는 시간 $P_i$가 주어졌을 때, 각 사람이 돈을 인출하는데 필요한 시간의 합의 최솟값을 구하는 프로그램을 작성하시오.

문제 요약:

  • 입력: 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 $P_i$가 주어진다. (1 ≤ $P_i$ ≤ 1,000)
  • 출력: 첫째 줄에 각 사람이 돈을 인출하는데 필요한 시간의 합의 최솟값을 출력한다.

제한 사항

  • 시간 제한: 1초
  • 메모리 제한: 256MB

입출력 예시

예시 1

입력 1

5
3 1 4 3 2

출력 1

32

문제 해결 전략

1. 접근 방법

  • 소요시간이 작은 순으로 정렬한다.
  • 첫 번째 사람부터 i번째 사람까지 대기 시간의 합은 아래와 같다. $(P_1) + (P_1 + P_2) + … + (P_1 + P_2 + … + P_{i-1} + P_i)$ $= n * P_1 + (n - 1) * P_2 + … + $ $(n - i - 1) * P_{i-1} + (n - i) * P_i$

코드 구현

n = int(input())
times = list(map(int, input().split()))

times.sort()

answer = 0

for index, time in enumerate(times):
    answer += (n - index) * time

print(answer)
  • 반복마다 N에서 3을 빼면서 N을 줄이고, number_of_bags에 1을 더한다.
  • N이 5가 되는 경우, number_of_bags에 N을 5로 나눈 몫을 더한 후, 반복문을 빠져나오고 number_of_bags를 출력한다.

시간 복잡도

  • times.sort()의 시간 복잡도는 $O(N\log N)$ 이다.
  • for index, time in enumerate(times) 반복문의 시간 복잡도는 $O(N)$ 이다.
  • 따라서, 전체 시간 복잡도는 $O(N\log N) + O(N) = O(N\log N)$ 이다.

개선할 점

  • 위의 코드는 직관적으로 왜 이런 코드를 사용하는지 이해하기 어렵다. 따라서, 누적합을 통해 더 직관적인 코드를 작성할 수 있다.
# 입력
n = int(input())  # 사람 수
p = list(map(int, input().split()))  # 각 사람이 인출하는 데 걸리는 시간

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

# 누적합 계산
total_time = 0
waiting_time = 0

for time in p:
    waiting_time += time
    total_time += waiting_time

# 출력
print(total_time)
  • 반복문이 실행될 때마다 $i$번째 사람의 대기 시간이 waiting_time에 더해지고 waiting_time은 total_time에 더해진다.
  • 반복문의 실행이 완료되면 첫 번째 사람부터 마지막 사람까지의 대기시간을 모두 합한 값이 total_time에 저장된다.

참고