백준 11399 - ATM

인원과 인원당 출금 시 걸리는 시간을 입력하면 모든 인원이 출력하는데 걸리는 시간의 최솟값을 구하는 문제입니다.

수학적으로 보면 쉽게 해결할 수 있습니다.
인원이 5명이라고 했을 때, 걸리는 시간이 각 a,b,c,d,e 라고 정의하겠습니다. 1번부터 5번까지 차례대로 출금한다고 했을 때 다음과 같은 식이 나옵니다.

이를 아래와 같이 정리할 수 있습니다.

이 식에서 출금하는 순서는 관계없습니다. 덧셈은 교환법칙이 성립하기에 어떤 순서로 더해도 결국 위 식이 산출됩니다.

즉, a가 가장 작은 수이고 e가 가장 큰 수인 경우 최솟값이 나오게 됩니다.

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

int main()
{
	int N;
	std::cin >> N;

	std::vector<int> times;

	for (int i = 0; i < N; i++)
	{
		int temp;
		std::cin >> temp;

		times.push_back(temp);
	}

	std::sort(times.begin(), times.end(), [](const int a, const int b) {return a < b; });

	int result = 0;
	for(int i = 0; i < N; i++)
	{
		result += times[i] * (N - i);
	}

	std::cout << result;

	return 0;
}