백준 : 11399번, ATM

문제 주소 : https://www.acmicpc.net/problem/11399

정답 비율 : 66.057% (2021.06.26 14:14 기준)

11399번: ATM

 

문제 조건 :

입력 : 첫 줄에는 사람의 수(n), 두 번째 줄에는 n명의 사람이 돈 인출하는데 걸리는 시간

출력 : 각 사람이 인출하는데 걸리는 시간의 합의 최솟값

시간 : 1초

 

문제 풀이 :

전형적인 그리디 알고리즘 문제로  Optimal Storage on tapes에 해당합니다.

예를 들어 3명이 존재하고 각 사람이 돈 인출하는데 걸리는 시간을 a, b, c로 하겠습니다. 하고 a -> b -> c 순서대로 돈을 인출한다고 가정하겠습니다. 

이때 각 순서에 해당하는 사람이 인출하는데 걸리는 시간은 다음과 같습니다.

첫 번째 순서 : a

두 번째 순서 : a + b

세 번째 순서 : a + b + c

 

수식으로 표시 : 총합 = a * 3 + b * 2 + c * 1

이를 일반화하면 다음과 같습니다. (n : 사람의 수, Vi : i번째 사람이 인출하는데 걸리는 시간)

총합 = V1 * (n - 1 + 1) + V2 * (n - 2 + 1) + V3 * (n - 3 + 1) + ... + Vn * ( n - n + 1)

 

또한 수식을 보면 뒷 순서일수록 곱하는 값이 작아지는 것을 확인할 수 있습니다.

 

따라서 최솟값을 구하려면 앞사람의 인출 시간은 뒷사람의 인출 시간보다 작아야 합니다. (오름 차순 정렬)

 

코드는 다음과 같습니다.

 

Python3

# solve 11399

size = int(input())
person = list(map(int, input().split()))
person.sort()
ans = 0
for p in person:
    ans += p * size
    size -= 1
print(ans)