[그리디] 백준 11399번 ATM Python 풀이

문제 요약

N명의 사람이 ATM 앞에 줄을 서 있다. 각자 돈을 인출하는데 필요한 시간이 다르기 때문에, 줄을 서는 순서가 달라지면 돈을 인출하는데 필요한 시간의 합이 달라진다. 한 사람이 인출하는데 필요한 시간은, 앞 사람의 시간에 본인 시간을 더하면 된다. (예: P1 = 3, P2 = 1, P3 = 4, P4 = 3, P5 = 2일 때, [P1, P2, P3, P4, P5] 순서일 때 시간은 [3, 1, 4, 3, 2]로 총 39분이 걸린다. 개별 시간은 P1은 3, P2는 3+1=4, P3은 3+1+4, P4는 3+1+4+3, P5는 3+1+4+3+2가 된다. [P2, P5, P1, P4, P3] 순서일 때 [1, 2, 3, 3, 4]로 총 32분이 걸린다. 개별 시간은 위와 같은 방법으로 구할 수 있음)

각 사람이 돈을 인출하는데 필요한 시간의 합의 최솟값을 구하는 프로그램을 작성하라.

 

백준 11399번 문제 바로가기

입력

첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000)

출력

첫째 줄에 각 사람이 돈을 인출하는데 필요한 시간의 합의 최솟값을 출력한다.

입출력 예시

입력	출력
5 　　　　　　3 1 4 3 2	32

코드

N = int(input())
time = list(map(int, input().split()))

time.sort()
now_time = 0
total_time = 0
for i in time:
    now_time += i
    total_time += now_time
print(total_time)

피드백

문제가 길어서 당황했지만 차근차근 읽으며 손으로 정리하니 문제가 이해되고, 풀이 방법이 떠올랐다.

문제를 보고 피보나치 수열과 비슷하다는 생각이 들어서 더 빨리 해결책을 찾을 수 있었다.