백준(Python) 11399: ATM 문제 풀이

문제

풀이

최소 시간을 계산하기 위해서는 작은 수부터 차례대로 정렬해야함을 파악해야하는 문제였다.

예시로 나온, [3, 1, 4, 3, 2]을 보자. 사람들이 기다려야 하는 시간은 모든 사람에게 누적되기 때문에, 가능한 시간이 적게 걸리는 사람들이 먼저 ATM에서 돈을 뽑고 빠져주는 것이 좋다.

따라서 순서가 [ 1, 2, 3, 3, 4] 가 되었을 때 최소 시간이 걸린다는 것을 다음처럼 알 수 있다.

1+ (1+2) + (1+2+3) + (1+ 2+ 3+3) + (1+ 2+ 3+ 3+ 4)

따라서, 코드는 N명 각각의 인출 시간의 합을 withdraw_sum이라는 변수에 저장하였고, final_sum에는 각각에 저장된 withdraw_sum을 합했다.

# 11399

# 사람의 수 입력 받기
N = int(input())

# 인출 시간 입력 받기
withdraw = list(map(int, input().split()))

# 인출 시간 작은 순으로 정렬
withdraw.sort()

# 시간 계산 하기
withdraw_sum = 0
final_sum = 0
for i in withdraw:
    withdraw_sum += i
    final_sum += withdraw_sum

print(final_sum)

느낀 점

뭔가, 그리디 알고리즘은 코딩 실력이 많이 필요한 것보다는 수학적으로 최선의 방법을 빨리 찾아내는 것이 중요한 것 같다.