[백준 C++] 11399 : ATM

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

그리디 알고리즘을 이용한 문제이다.

---

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
	int N, ans = 0;
	cin >> N;
	vector<int> list = vector<int>(N, 0);

	for (int i = 0; i < N; i++)
		cin >> list.at(i);

	sort(list.begin(), list.end());

	for (int i = 0; i < N; i++)
		ans += list.at(i) * (N - i);

	cout << ans << endl;

	return 0;
}

문제에 적혀있는데로 P1 = 3, P2 = 1, P3 = 4, P4 = 3, P5 = 2 인 경우일 때, [1, 2, 3, 4, 5] 순서이면 다음과 같이 시간이 소요된다.

 

즉, 처음 시작하는 사람의 소요시간 * N 으로 시작하여 N이 1까지 줄어들면 총 합을 구할 수 있다.

최소값을 구해야 하므로 가장 적은 시간이 N개부터 시작하여 가장 큰 시간이 1로 끝나면 최소값을 구할 수 있을 것이다.

 

sort로 정렬한 후에 값을 ans에 더해 정답을 구해주었다.