[백준] 11399 ATM with C++

문제설명

---

입출력 예제

---

개념

　각 사람이 돈을 인출하는 데 필요한 시간 합의 최솟값을 출력하는 문제다. 대표적인 그리디 알고리즘으로 효율적으로 해결할 수 있는 문제로서, 실행 시간이 가장 짧은 프로세스부터 우선적으로 처리하는 최단 작업 우선 스케줄링 방식을 이용하면 된다. 여기서 돈을 인출하는데 걸리는 시간을 작업으로 보고, 이 작업들을 가장 짧은 것부터 처리하면 모든 사람이 돈을 인출하는데 필요한 최소 시간을 구할 수 있다.

---

풀이

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
	int N;
	cin >> N;
	vector<int> v(N);
	int* sum = new int[N];

	for (int i = 0; i < N; ++i)
		cin >> v[i];
	sort(v.begin(), v.end());

	int res = sum[0] = v[0];
	for (int i = 1; i < N; ++i)
	{
		sum[i] = sum[i - 1] + v[i];
		res += sum[i];
	}

	cout << res;
}

　실행 시간이 짧은 것부터 오름차순으로 정렬한 후에, 부분합 개념을 이용하여 합을 출력하면 된다.