백준] 1758 - 알바생 강호

시간 제한 : 2초

메모리 제한 : 128MB

입력

첫째 줄에 스타박스 앞에 서 있는 사람의 수 N이 주어진다. N은 100,000보다 작은 자연수이다. 둘째 줄부터 총 N개의 줄에 각 사람이 주려고 하는 팁이 주어진다. 팁은 100,000보다 작거나 같은 자연수이다.

출력

강호가 받을 수 있는 팁의 최대값을 출력한다.

소스코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
using namespace std;
int main(void)
{
	int n, tmp;
	long long sum = 0;
	vector<int> arr;
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> tmp;
		arr.push_back(tmp);
	}
	sort(arr.begin(), arr.end(), greater<int>());
	for (int i = 0; i < n; i++)
	{
		if (arr[i] - i <= 0)
			break;
		sum += (arr[i] - i);
	}
	cout << sum;
}

Tip

문제는 간단하게 풀린다. 기본적으로 팁을 많이 받으려면 팁을 많이 줄 생각을 하고 있는 사람들을 우선 순위로 배치하면 되고, 이는 정렬로 해결한다. 정렬한 값을 바탕으로 적합하게 처리하면 된다.