[C++] 백준 11399번 : ATM

- 문제

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

11399번: ATM

 

 

---

- 구상

사실 최소를 찾기만 하면 되기에, 결과론적으로 생각하면 편하다.

 

➡어찌됐건 총 기다린 시간을 생각해보면,

1.  1번째로 수행한 사람의 시간은 N번 반복해서 더해질 것이고,
2.  2번째로 수행한 사람의 시간은 N-1번 반복해서 더해질 것이고,
3. ...
4.  N번째로 수행한 사람의 시간은 뒤에 사람이 더 없으니, 1번만 더해질 것이다.

➡ 이 점을 이용해서 돈을 인출하는 데에 가장 적은 시간이 걸리는 사람을 첫번째로, 가장 많은 시간이 걸리는 사람을 마지막으로, 즉 오름차순으로 줄 세우게 된다면, 총 기다린 시간은 최소가 될 수 있다.

 

 

---

 

 

- 구현

swap()함수를 간만에 사용하였다. swap()은 사실 많이 쓰여서 그런지 algorithm 라이브러리에 있어서 별도의 구현이 필요 없다.

여기선 min_idx라는 최솟값의 인덱스를 return하는 함수를 사용했는데, 아래의 방식을 그대로 사용하면 쓸 수 있다. 참고하자.

#include <iostream>
#include <vector>
#include <algorithm>
#define endl '\n'
using namespace std;

int main() {

	ios_base::sync_with_stdio(false); cout.tie(NULL), cin.tie(NULL);

	int N;
	cin >> N;
	vector<int> P(N);

	for (int& elem : P) {
		cin >> elem;
	}

	int sum=0, min_idx;

	for (int i = 0; i < N; i++) {
		sum += (*min_element(P.begin(), P.end()))*(N-i);
		min_idx = min_element(P.begin(), P.end())-P.begin();
		swap(P[min_idx], P[N - i - 1]);
		P.pop_back();
	}

	cout << sum;


	
	return 0;

}