Algorithm/문제
[백준 온라인 저지] ATM
Lim Seung Hyun
2022. 2. 12. 16:32
문제 출처
11399번: ATM
첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000)
www.acmicpc.net
문제 해설
- 사람이 N명이고, 각 사람이 돈을 인출하는 데 걸리는 시간을 주어진다.
- ATM 기기가 하나밖에 없기 때문에 줄을 잘 배정하여 모든 사람이 돈을 인출하는 게 덜리는 시간의 합이 최소화하도록 하기
- 이 문제의 경우, 1번이 인출해야 2번이 인출이 가능하고 2번이 인출해야 3번이 인출이 가능하다.
- 즉, n번째 사람이 인출하려면 n1, n2, .... , n-1번 사람이 모두 인출이 되어야 한다.
- 이를 수식으로 변경하면 Tn = T1 + T2 + ... + Tn-1 (T는 인출 시간, n은 순서)
- 시간의 합이 최소가 되기 위해서는 앞선 사람의 인출하는 시간이 최소가 되어야 한다.
- 3명이 인출하게 된다면 총 인출 시간은 (3T1 + 2T2 + T3)가 될 것이다.
- 여기서 합계가 최소가 되려면 T1이 제일 작은 수가 되어야 한다.
- 따라서, 이 문제에서 돈을 인출하는데 걸리는 시간을 오름차순으로 정렬해서 합계를 구하면 문제는 해결될 것으로 예상
나의 풀이 (Python3)
# source : https://www.acmicpc.net/problem/11399
import sys
N = int(sys.stdin.readline().strip())
P = list(map(int, sys.stdin.readline().strip().split()))
answer = 0
P = sorted(P)
for i in range(N):
answer += sum(P[:i+1])
print(answer)
728x90