(백준/C++) 11399_ATM

11399번: ATM (acmicpc.net) 문제는 탐욕(그리디) 알고리즘으로 풀 수 있는 문제입니다.

탐욕 알고리즘(Greedy Algorithm)이란, 매 순간 최적이라고 생각되는 방법을 선택하는 방식으로 문제를 해결하는 알고리즘입니다.

즉, 다른 경우의 수가 없이 현 문제에서 가장 좋아 보이는 것을 선택해 나가다보면 문제가 풀리는 알고리즘 입니다.

따라서, ATM 문제는 각 사람이 돈을 인출하는데 걸리는 시간을 최소화하면 전체 시간도 최소화 됩니다.

---

접근법

이 문제의 핵심은 “각 사람이 돈을 인출하는데 걸리는 시간을 최소화하면 전체 시간도 최소화된다” 는 것입니다.

따라서 각 사람이 돈을 인출하는 시간을 오름차순으로 정렬하면, 앞 사람이 돈을 인출하는 시간이 최소가 되므로 전체 시간도 최소가 됩니다.

---

풀이

각 사람이 돈을 인출하는 시간을 오름차순으로 정렬한 후, 각 사람이 돈을 인출하는 데 필요한 시간을 누적하여 계산합니다.

이렇게 하면 각 사람이 돈을 인출하는 데 필요한 시간의 합의 최솟값을 구할 수 있습니다.

이때, 현재 사람이 인출하는 데 걸리는 시간을 남은 사람에게 전부 누적해 가면 각 사람이 돈을 인출하는 데 필요한 총 누적 시간이 계산 됩니다.

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

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

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

	vector<int> times(N);
	for (int i = 0; i < N; i++)
		cin >> times[i];

	sort(times.begin(), times.end());

	for (int i = 0; i < N; i++)
	{
		result += times[i] * (N - i); // 누적 합을 이용하여 나머지 대기 인원에 현재 시간을 전부 추가한다.
	}

	cout << result;
}