[c++] 백준 11399 ATM

백준 단계별로 풀어보기 [그리디 알고리즘] ATM

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

11399번: ATM

 

[풀이]

각 사람이 돈을 인출하는데 필요한 시간의 합의 최솟값은 Pi가 가장 작은 사람 순으로 돈을 인출할 때 구할 수 있다. 따라서 그리디 알고리즘이 적용되는 문제이므로 입력받은 Pi를 오름차순으로 정렬 후 누적합을 구하여 구할 수 있다.

 

[코드]

#include <iostream>
#include <algorithm>

int main() {
	int num;
	std::cin >> num;
	int* wait_time = new int[num];

	for (int i = 0; i < num; i++) {
		std::cin >> wait_time[i];
	}

	std::sort(wait_time, wait_time + num);

	int sum = 0;
	for (int i = num; i >= 0; i--) {
		for(int j=0; j<i; j++)
			sum += wait_time[j];
	}

	std::cout << sum;

	delete[] wait_time;
	return 0;
}