알바생 강호

2017-01-10 03:19:38 | 조회수 1233



※이 설명은 공식 솔루션이 아닌 작성자의 개인적인 솔루션입니다.


손님으로부터 받을 수 있는 돈은 정해져 있고, 등수가 뒤로 밀려날 수록 받을 수 있는 금액에서 1원씩 빠진 금액을 받게 됩니다. 즉, 빠지는 값이 고정적으로 정해진 상태에서 손님을 배치하는 문제입니다.


직감적으로 큰 돈을 가진 손님을 앞에 둘 수록 유리하다는 것을 알 수 있습니다. 왜냐하면, 큰 돈을 가진 손님을 뒤에 배치할 경우, 작은 돈을 가진 손님과 비슷해지거나 손해가 되기 때문입니다. 따라서 큰 돈을 받을 수 있는 손님부터 정렬하여, 실제로 받게 되는 돈을 계산하면 되는 문제입니다.


단, 10만명이 최대 10만원까지 팁을 줄 수 있으므로, 답의 최댓값이 int 범위를 넘어갈 수 있다는 점에 유의하세요.


※해당 소스코드는 참고용이며, 최적화 된 공식 솔루션 소스가 아닙니다. 이 소스를 그대로 복사하여 이용, 또는 제출하는 행위에 대한 불이익은 책임지지 않습니다.

#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
typedef long long ll;

int w[100001];
int main()
{
    int n;
    long long ans = 0;
    cin >> n;
    for (int i = 0; i < n; i++) cin >> w[i];
    sort(w, w + n);

    for (int i = n - 1, j = 1; i >= 0; i--, j++)
    {
        int tip = w[i] - (j - 1);
        ans += tip >= 0 ? tip : 0;
    }
    cout << ans;
}


알바생 강호 - 알고리즘닷컴
여기서는 https://acmicpc.net 의 문제를 기반으로 한 설명과 소스코드를 포스팅합니다.

36 개의 글