[백준 BOJ][C++]11399번 ATM 풀이: 그리디 알고리즘

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

11399번: ATM

 

 각 사람이 돈을 인출하는데 필요한 시간의 합이 최소가 되려면 시간이 적게 걸리는 사람일수록 앞에 서야합니다. 

 

 입력으로 들어온 시간 Pi를 오름차순으로 정렬한 뒤, 각 시간을 점차 더해주면 됩니다. 

 

 시간 Pi의 자료구조로 배열을 사용해도 되지만, 정렬하기 귀찮으니 저는 우선순위큐를 사용했습니다.

 

 C++ 컨테이너인 priority_queue를 사용하여 push와 동시에 오름차순으로 정렬되게 하였습니다. 

 

#include<iostream>
#include<queue>
#include<algorithm>

using namespace std;

int main(void) {

	int n;
	priority_queue<int, vector<int>, greater<int>> p; //시간 우선순위큐

	cin >> n;

	for (int i = 0; i < n; i++) {
		int temp;
		cin >> temp;
		p.push(temp);
	}

	int prev;
	int result;

	prev = result = p.top();
	p.pop();

	while (!p.empty()) {
		prev = prev + p.top(); //i번째 사람 시간=앞 사람 시간+i번째 사람이 인출하는데 걸리는 시간
		result += prev;
		p.pop();
	}

	cout << result;

	return 0;
}