[백준 1758번] 알바생 강호

문제 링크: https://www.acmicpc.net/problem/1758

1758번: 알바생 강호

<문제 풀이> 그리디, 정렬 알고리즘

 

팁 - (받은 등수 - 1)

 

위 식을 계산했을 때 0보다 작은 경우는 팁을 누적하지 않습니다.

전체 팁의 합을 최댓값으로 만드는 최적의 해는 사람을 배치할 때 팁을 적게 주는 사람을 최대한 뒤로 보내는 것입니다.

 

예를 들어

50원을 주는 사람이 1등이고, 10원을 주는 사람이 100등이라고 할 때 팁은 다음과 같이 계산됩니다.

 

50 - (1 - 1) = 50
10 -(100 -1 ) = 0

총 팁 : 50

 

50원을 주는 사람을 100등, 10원을 주는 사람을 1등이라고 할 때 팁은 다음과 같이 계산됩니다.

50 - (100 - 1) == 0

10 - (1 - 1) = 10

총 팁: 10

 

위 예시를 보면 뒤에 오는 사람은 식의 값이 0보다 작게 되어서 팁을 누적하지 않습니다.

둘 중에 한 명의 팁을 누적하지 않을 거라면 최대한 팁을 적게 주는 사람을 뒤로 보내 누적하지 않는 것이 최적의 해가 되는 것을 알 수 있습니다.

 

따라서 팁을 기준으로 내림차순 정렬한 뒤 식의 값을 누적하면 됩니다.

 

<C++소스코드>

#include<iostream>
#include<algorithm>
#include<functional>
using namespace std;
 
typedef long long ll;
 
int seq[100001];
 
int main() {
    ios_base::sync_with_stdio(false);
 
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> seq[i];
    }
    sort(seq, seq + n, greater<int>());
    ll ans = 0;
    for (int i = 0; i < n; i++) {
        int m = seq[i] - i;
        if (m < 0) continue;
        ans += m;
    }
    cout << ans;
    return 0;
}