인하은행에는 ATM이 1대밖에 없다. 지금 이 ATM앞에 N명의 사람들이 줄을 서있다.
사람은 1번부터 N번까지 번호가 매겨져 있으며, i번 사람이 돈을 인출하는데 걸리는 시간은 Pi분이다.
줄을 서 있는 사람의 수 N과 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어졌을 때, 각 사람이 돈을 인출하는데 필요한 시간의 합의 최솟값을 구하는 프로그램을 작성하시오.
첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000)
첫째 줄에 각 사람이 돈을 인출하는데 필요한 시간의 합의 최솟값을 출력한다.
5
3 1 4 3 2
32
즉 이 문제를 설명하자면, 모든 사람들이 기다리는 시간을 포함해서 인출을 완료하는 시간 누적합을 구하는 것이다.
마치 운영체제 스케줄러가 생각나는데.. ㅎ
사실 인출에 걸리는 시간을 줄일수는 없기 때문에 기다리는 시간의 총 합을 줄일 수 밖에 없다.
따라서 빨리 끝내는 사람부터 정렬시키면 된다.