[Python] 백준 11399. ATM

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

11399번: ATM

문제 설명:

줄을 서 있는 사람의 대기시간이 주어졌을때 각 사람이 돈을 인출하는데 필요한 시간의 합의 최솟값을 구하는 문제이다.

3 1 4 3 2 가 주어지면 1번 = 3분 / 2번 = 1분 / 3번 = 4분 / 4번 = 3분 / 5번 = 2분의 시간을 쓴다.

 

순서가 1번 -> 2번 -> 3번 -> 4번 -> 5번 이면

1번이 쓰는 시간 : 3분

2번이 쓰는 시간 : 3 + 1 -> 4분

3번이 쓰는 시간 : 3 + 1 + 4 -> 8분

4번이 쓰는 시간 : 3 + 1 + 4 + 3 -> 11분

5번이 쓰는 시간 : 3  + 1+ 4 + 3 + 2 -> 13분

 

총 39분의 시간이 걸린다.

 

순서 2번 -> 5번 -> 1번 -> 4번 -> 3번 이면

1번이 쓰는 시간 : 1분

2번이 쓰는 시간 : 1 + 2 분

3번이 쓰는 시간 : 1 + 2 + 3 분

4번이 쓰는 시간 : 1 + 2 + 3 + 3 분

5번이 쓰는 시간 : 1 + 2 + 3 + 3 + 4 분

 

총 32분의 시간이 걸린다.

 

자세히 보면 앞에 사람의 숫자가 작을수록 최솟값을 찾을 수 있다. -> 정렬을 이용한다.

 

풀이 설계

• 받은 리스트를 sort한다.
• 숫자를 받아 합을 구한다. 1번이 쓰는 시간의 합 / 2번이 쓰는 시간의 합
• 합을 다시 총 소요시간에 더해준다.

 

n = int(input())
nlist = list(map(int, input().split()))
nlist = sorted(nlist)

sum = 0
result = 0
for num in nlist:
	# 숫자를 받아 합을 구한다. 1번이 쓰는 시간의 합 / 2번이 쓰는 시간의 합 ...
    sum += num
    # 합을 다시 총 소요시간에 더해준다.
    result += sum

print(result)