C++ / 백준 / 1758 / 알바생 강호

문제

 

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

1758번: 알바생 강호

문제풀이

 

팁이 음수가 될 수 는 없다, 음수가 될 경우 팁은 0원이다.

뒤로 갈수록 등수가 늘어나므로 팁은 점점 줄어들것이다.

팁이 0원이 되든 -100원이 되든 똑같은 0원이므로, 팁을 내림차순으로 하여 받으면 최대로 받을 수 있다.

 

코드

#include <iostream>
#include <vector>
#include <algorithm>
#define ll long long
using namespace std;

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

	ll N(0), idx(0), answer(0);
	cin >> N;
	vector<ll>tip(N, 0);

	for (idx = 0; idx < N; ++idx) {
		cin >> tip[idx];
	}

	sort(tip.begin(), tip.end(), greater<ll>());

	for (idx = 0; idx < N; ++idx) {
		answer += max(tip[idx] - idx, (long long)0);
	}
	cout << answer;
}