백준 11399번 ATM

 

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

11399번: ATM

 

 

Greedy 알고리즘은 가장 큰 것, 작은 것 등 원하는 방향을 기준으로 규칙을 지키면서 접근하면 된다.

정렬 알고리즘을 함께 사용하는 경우가 많다.

 

돈을 인출하는데 필요한 시간의 합이 최소값이 되도록 해야 하므로 돈을 인출하는데 가장 많은 시간이 걸리는 사람은 마지막에 인출해야 한다. 마찬가지로 돈을 인출하는데 가장 적은 시간이 걸리는 사람이 가장 먼저 돈을 인출하는 것이 좋다. 따라서 우선 오름차순으로 정렬한 뒤 접근하는 것이 좋다.

 

입력으로

5

3 1 4 3 2이 주어졌을 때 오름차순 정렬하면 1, 2, 3, 3, 4가 된다. 

 

사람별로 대기해야 하는 시간의 합을 모두 더하면 아래와 같은 규칙을 찾을 수 있으므로 이를 반복문으로 쉽게 구현하면 된다.

1

1+2

1+2+3

1+2+3+3

1+2+3+3+4

 

#include <iostream>
#include <algorithm>

using namespace std;

int main() {

	int time[1000] = { 0 };
	int n;
	int cnt;
	int result = 0;

	cin >> n;
	cnt = n;
	for (int i = 0; i < n; i++) {
		cin >> time[i];
	}

	sort(time, time + n);


	for (int i = 0; i < n; i++) {
		result += cnt * time[i];
		cnt--;
	}

	cout << result;


	return 0;
}