[BOJ/1758/C++] 알바생 강호

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

문제

• 스타박스는 손님을 입장시킬 때 독특한 방법으로 입장시킨다.

• 스타박스에서는 손님을 8시가 될 때 까지, 문앞에 줄 세워 놓는다. 그리고 8시가 되는 순간 손님들은 모두 입구에서 커피를 하나씩 받고, 자리로 간다. 강호는 입구에서 커피를 하나씩 주는 역할을 한다.

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

조건

• 첫째 줄에 스타박스 앞에 서 있는 사람의 수 N이 주어진다. N은 100,000보다 작거나 같은 자연수이다.
• 팁은 100,000보다 작거나 같은 자연수이다.

풀이

위와 같은 문제는 반례가 있는지 한번은 생각해봐야 하는 문제이다. 물론, 경험적으로 바로 내림차순으로 정렬하면 크게 문제는 없겠구나라는 걸 알 수 있지만, 진짜 그런지 여러가지 반례들을 생각해봐야한다.

예를들어, [1,2,3,4]에서 발생할 수 있는 손실은 결국 -6원이다. 이때, -1,-2,-3에서 최대로 이득을 발생하기 위해서는 제일 큰돈은 손실 없이 얻고, 제일 작은 돈은 제일 큰 손실로(감가가 없기 때문에, 마이너스가 되면 0) 하게된다면, 최대 효용을 얻을 수 있다는걸 직관적으로 알 수 있다.

만약 감가가 있다면 손실을 감당할 수 있게끔 배치를 잘 해야한다.

#include <bits/stdc++.h>
#define fastio cin.tie(0)->sync_with_stdio(0)

using namespace std;

int N;
int customer[100001];

bool comp(int a, int b)
{
  return a > b;
}

int main()
{
  fastio;
  cin >> N;
  long long total = 0;
  for (int i = 0; i < N; i++)
  {
    cin >> customer[i];
  }
  sort(customer, customer + N, comp);

  int tip = 0;
  for (int i = 0; i < N; i++)
  {
    tip = customer[i] - i;
    if (tip < 0)
      tip = 0;
    total += tip;
  }
  cout << total << '\n';
  return 0;
}