백준 1758 - 알바생 강호

www.acmicpc.net/problem/1758

1758번: 알바생 강호

고객이 기다리는 순번이 하나 증가할수록 주려는 팁에 패널티가 1씩 생길 때(역으로 돈을 갈취하지는 않는다.), 강호가 가장 많이 팁을 벌 수 있도록 하여 고객을 배치할 때 벌어들이는 팁을 구하는 문제이다.

 

높은 금액의 팁을 주는 고객일수록 적은 패널티를 받게 해야 최적해에 이를 수 있다.

따라서 팁을 많이 주는 순서대로 내림차순 정렬하여 받을 수 있는 팁을 계산하면 최적해를 구할 수 있다.

 

전체코드

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

ll res;

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

    int n; cin >> n;
    vector<int> pay(n);

    for (int i = 0; i < n; ++i)
        cin >> pay[i];
    
    sort(pay.begin(), pay.end(), greater<int>());

    for (int j = 0; j < n; ++j)
        res += max(0, pay[j] - j);
    cout << res;
}