[c++] 백준 1758: 알바생 강호

[c++] 백준 1758: 알바생 강호

🥈실버 4

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

1758번: 알바생 강호

---

손님들은 자기가 커피를 몇 번째 받는지에 따라 팁을 다른 액수로 강호에게 준다.
각 손님은 강호에게 원래 주려고 생각했던 돈 - (받은 등수 - 1) 만큼의 팁을 강호에게 준다.
만약, 위의 식으로 나온 값이 음수라면, 강호는 팁을 받을 수 없다.

 

 

접근

돈을 많이 주려고 한 사람이 앞에 설 수록 강호가 받을 수 있는 팁의 액수가 커진다.

입력값을 받은 다음에 내림차순으로 정렬하고 공식에 맞게 계산하면 된다.

받은 등수가 곧 배열에서의 인덱스 i+1이기 때문에 

돈 - i로 계산하면 편하다.

 

대신 int로 값을 할당하면 문제가 틀리게 되는 경우가 있으니 long long으로 선언하도록 하자.

 

코드

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
  ll N;
  cin >> N;
  ll arr[N];
  for (ll i = 0 ; i < N; i++) {
    cin >> arr[i];
  }
  sort(arr, arr+N, greater<>()); // 내림차순

  ll ans = 0;
  for (ll i = 0; i < N; i++) {
    ll tmp = arr[i] - i;  // arr[i] - (i+1 -1)과 같다.
    if (tmp > 0) ans += tmp;
  }
  cout << ans;
  return 0;
}