[백준] 11399 ATM - C++

문제) ATM기에 줄을 뽑기 위해 사람들이 서있다. 각 사람마다 인출하는 데 걸리는 시간이 다르다고 했을 때, 필요한 시간의 합의 최솟값을 구하는 프로그램을 만들어보자.

    첫째 줄에 사람의 수 n과 인출하는데 걸리는 시간 Pi가 주어진다.

    시간 제한은 1초, 메모리 제한은 256MB이다.

 

n의 범위가 1000으로 작기 때문에 O(n^2) 정렬을 써도 무방하다. 여기서는 그냥 알고리즘 헤더파일의 sort로 nlogn을 사용했다. 먼저 사용하는데 걸리는 시간이 작은 순으로 정렬하고 합배열로 각 시간의 합을 더해주면 풀 수 있는 문제다.

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

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

	int n;
	cin >> n;

	vector<int> a(n, 0);
	vector<int> s(n, 0);

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

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

	s[0] = a[0];

	for (int i = 1; i < n; i++)
	{
		s[i] = s[i - 1] + a[i];
	}

	int sum = 0;

	for (int i = 0; i < n; i++)
	{
		sum = sum += s[i];
	}

	cout << sum;

	return 0;
}