ATM (백준 - 11399번)

정렬을 할 줄 안다면 정말 쉬운 문제이다. 시간의 합이 최소가 되기 위해서는 각 사람이 돈을 인출하는데 필요한 시간을 오름차순으로 정렬하면 된다.

 

정렬 전

[3 1 4 3 2]

3

3 + 1 = 4

3 + 1 + 4 = 8

3 + 1 + 4 + 3 = 11

3 + 1 + 4 + 3 + 2 = 13

 

3 + 4 + 8 + 11 + 13 = 39

 

정렬 후

[1 2 3 3 4]

1

1 + 2 = 3

1 + 2 + 3 = 6

1 + 2 + 3 + 3 = 9

1 + 2 + 3 + 3 + 4 + 13

 

1 + 3 + 6 + 9 + 13 = 32 

 

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

int main()
{
	int personCount = 0;
	int* personTime = nullptr;
	int sum = 0;
	cin >> personCount;

	personTime = new int[personCount];

	for (int i = 0; i < personCount; ++i)
	{
		int input = 0;
		cin >> input;
		personTime[i] = input;
	}

	sort(personTime, personTime + personCount);

	for (int i = 0; i < personCount; ++i)
	{
		tempSum += personTime[i];
		sum += tempSum;
	}

	cout << sum << endl;
	delete[] personTime;
}

입력 수와 그에 맞는 각 사람의 인출에 필요한 시간을 입력 받은 배열을 오름차순으로 정렬해준 후 임시 값에 순차적으로 더해주면서 그걸 최종 값에 또 더해주면 된다. 보다 빠른 정렬을 위해 구현이 빠른 버블 정렬을 사용할 수 있었지만 sort() 메서드를 사용하였다.