백준 11399 - ATM

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

11399번: ATM

n = int(input())
arr= list(map(int, input().split()))

arr.sort()
time_arr = []
for i in range(len(arr)):
    t = sum(arr[:i+1])
    time_arr.append(t)

print(sum(time_arr))

문제 안에 솔루션이 담겨 있는 문제다. 다시 말해서, 시간 소요가 적은 사람들부터 우선적으로 ATM을 해결할 수 있게 하는 경우의 수가 전체 이용인원의 이용시간의 합을 최소로 만들 수 있는 경우의 수라는 이야기가 된다.

 

그렇기 때문에 시간소요가 적은 사람들부터 쓸 수 있게, sort를 먼저 해 주고,

a[0]번째로 쓰는 사람은 0번이 이용하는 시간만을 더해주고 time_arr에 그 값을 저장한다.

a[1]번째로 쓰는 사람은 0+1번이 이용하는 시간을 더해주고 time_arr에 그 값을 저장한다.

a[2]번쨰로 쓰는 사람은 0+1+2번이 이용하는 시간을 더해주고 time_arr에 그 값을 저장한다.

...

이후 time_arr의 각 값의 합계를 출력한다.

 

greedy_algorithm 문제인데, 그 중 가장 기초적인 내용을 담은 데다가 어떻게 하면 greedy하게 선택할 수 있는지를 문제에서 알려줘서 쉽게 풀 수 있는 문제다.