[Baekjoon] 11399번: ATM

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

11399번: ATM

 

---

 

문제 해결 과정

착안

뒤에서 기다리는 사람이 돈을 인출하려면 자신보다 앞 번호에 대기 중인 사람들이 모두 돈을 인출해야하므로, 각 사람이 돈을 인출하는데 필요한 시간의 총합을 최소로 하기 위해서는 인출하는 시간이 짧은 사람을 앞에 배치하여야 한다. 따라서, 우선순위 큐(priority queue) 자료 구조를 이용하여 인출하는 시간의 정보를 저장한 다음, 최소 인출시간인 사람부터 순차적으로 우선순위 큐에서 추출하는 방식을 활용해 ATM 대기 인원을 배치하는 방법으로 문제를 해결하고자 하였다.

* 참고) 최소 힙(minimum heap) 트리 자료 구조를 활용하거나 그냥 배열에 입력받아 정렬하여 해결할 수도 있다.

 

구현

정렬 조건을 std::greater<int>로 하는 std::priority_queue<> 클래스를 활용해 최소 인출 시간이 항상 top에 위치하는 우선순위 큐를 선언하여 문제를 해결하였다.

 

$i$번째 사람이 돈을 인출하는 시간을 $P_i$라고 하면, $n$명의 대기 인원이 모두 돈을 인출하는데 걸리는 시간의 총합은

$$\sum_{i=1}^{n} P_i = n P_1 + (n-1) P_2 + \cdots + 2 P_{n-1} + P_n$$

이다.

 

[스포 주의] 아래 '더보기'를 누르면 코드가 나오니 주의하세요~

#include <iostream>
#include <queue>

using namespace std;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	int N, Sum = 0;
	cin >> N;

	priority_queue<int, vector<int>, greater<>> pq;
	for (int i = 0; i < N; i++)
	{
		int time;
		cin >> time;
		pq.emplace(time);
	}

	while (!pq.empty())
	{
		int time = pq.top();
		pq.pop();

		Sum += time * N--;
	}

	cout << Sum << "\n";
	return 0;
}

 

실행 결과