백준 11399번: ATM

[문제 링크]

11399번: ATM

---

간단한 그리디 알고리즘 문제였다.

인출하는데 걸리는 시간이 짧은 사람부터 먼저 인출하는 것이 항상 최적해를 보장하기 때문에, 입력받은 배열을 오름차순 정렬한 후 인출 시간이 짧은 사람부터 차례대로 계산해주면 원하는 결과를 얻을 수 있다.

---

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

void QuickSort(vector<int>& data, int start, int end)
{
	if (start >= end) return;

	int pivot = start;
	int i = start + 1;
	int j = end;

	while (i <= j)
	{
		while (i <= end && data[i] <= data[pivot])
			i++;

		while (j > start && data[j] >= data[pivot])
			j--;

		if (i > j)
		{
			int temp = data[pivot];
			data[pivot] = data[j];
			data[j] = temp;
		}

		else
		{
			int temp = data[i];
			data[i] = data[j];
			data[j] = temp;
		}
	}

	QuickSort(data, start, j - 1);
	QuickSort(data, j + 1, end);
}

int Greedy(vector<int>& wait, int N)
{
	QuickSort(wait, 0, N-1);

	int time = 0, res = 0;

	for (int i = 0; i < N; i++)
	{
		time = (time + wait[i]);
		res += time;
	}

	return res;
}

int main(void)
{
	int N;
	cin >> N;
	
	vector<int> wait;
	for (int i = 0; i < N; i++)
	{
		int P;
		cin >> P;
		wait.push_back(P);
	}

	cout << Greedy(wait, N) << endl;

	return 0;
}

알고리즘 200일 프로젝트 - 110 day