그리디 | 백준 11399 ATM

문제

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

줄을 서 있는 사람의 수 N과 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어졌을 때,

각 사람이 돈을 인출하는데 필요한 시간의 합의 최솟값

 

입력

• 첫째 줄: 사람의 수 N
• 둘째 줄: 각 사람이 돈을 인출하는데 걸리는 시간 Pi

 

출력

• 각 사람이 돈을 인출하는데 필요한 시간의 합의 최솟값

 

풀이

import sys
input = sys.stdin.readline
 
N = int(input().strip())
P = list(map(int, input().split()))
P.sort()

result = 0
prefix = 0
for time in P:
    prefix += time
    result += last
  
print(result)

 

앞사람이 걸리는 시간만큼 뒷사람은 기다려야 하므로,

돈을 인출하는데 걸리는 시간의 오름차순으로 인출해야 최소 시간으로 돈을 인출할 수 있다.

또한 누적합을 알고 있어야 현재 순서인 사람이 돈을 인출하기 위해 걸린 시간을 계산할 수 있다.

따라서 이와 같은 과정으로 계산한다.

 

1. P를 오름차순으로 정렬한다.

2. 순차적으로 P를 돌면서 누적합을 계산한다.

3. 계산한 누적합을 result에 더해준다.