[문제]
인하 은행에는 ATM이 1대 밖에 없다. 지금 이 ATM 앞에 N명의 사림이 줄을 서 있다. 사람은 1번부터 N번까지 번호가 매겨져 있으며, i번 사람이 돈을 인출하는데 걸리는 시간은 pi 분이다.
사람들이 줄얼 서는 순서에 따라서, 돈을 인출하는데 필요한 시간의 합이 달라지게 된다. 예를 들어, 총 5명이 있고, P1 = 3, P2 = 1, P3 = 4, P4 = 3, P5 = 2 인 경우를 생각해보자. [1,2,3,4,5] 의 순서로 줄을 선다면, 1번 사람은 3분만에 돈을 뽑을 수 있따. 2번 사람은 1번 사람이 돈을 뽑을 때까지 기다려야 하기 때문에, 3+1=4 분이 걸리게 된다. 3번 사람은 1번, 2번 사람이 돈을 뽑을 때까지 기다려야하기 때문에, 총 3+1+4=8 분이 필요하게 된다. 4번 사람은 3+1+4+3=11분, 5번 사람은 3+1+4+33+2=13분이 걸리게 된다. 이 경우에 각 사람이 돈을 인출하는데 필요한 시가느이 합은 3+4+8+11+13=39 분이 된다.
줄을 [2,5,1,4,3] 순서로 줄을 서면, 2번 사람은 1분만에, 5번 사람은 1+2=3분, 1번 사람은 1+2+3=6분, 4번 사람은 1+2+3+4=9분, 3번 사람은 1+2+3+3+$=13 분이 걸리게 된다. 각 사람이 돈을 인출하는데 필요한 시간의 합은 1+3+6+9+13=32분이다. 이 방법보다 더 필요한 시간의 합을 최소로 만들 수는 없다.
줄을 서 있는 사람의 수 N과 각 사람이 돈을 인출하는데 필요한 시간의 합의 최솟값을 구하는 프로그램을 작성하시오.
[입력]
첫째 줄에 사람의 수 N(1<=N<=1000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 pi가 주어진다. (1<=Pi<=1000)
[출력]
첫째 줄에 각 사람이 돈을 인출하는데 필요한 시간의 합의 최솟값을 출력한다.
[예제 입력1]
5
3 1 4 3 2
[예제 출력 1]
32
[문제풀이]
먼저 , 대기 시간을 줄여야 함으로 정렬한다.
정렬한 Pi를 순차적으로 탐색하며, N-i 번 만큼 대기 인원이 발생할 것으므로 곱하여 더해준다.
[코드]
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main() {
int N;
cin >> N;
vector<int> time;
int answer = 0;
for (int i = 0; i < N; i++) {
int temp;
cin >> temp;
time.push_back(temp);
}
sort(time.begin(), time.end());
for (int i = 0; i < time.size(); i++) {
answer += time[i] * (N-i);
}
cout << answer;
return 0;
}