[C/C++] 백준 #1758 알바생 강호(탐욕)

이번 문제는 팁을 최대로 받기 위해서 적절한 전략을 세울 필요가 있습니다.

 

사실 모두 꽤 많은 팁을 생각했다면, 어떤 순으로 커피를 전달해도 결과는 같습니다.

예를 들어서 3명의 손님이 10원, 20원, 30원을 생각했다면, 순서와 관계가 없이 받는 팁은 같습니다.

 

cups of coffee

 

알바생 강호는 10원, 19원, 28원을 받게 되겠죠.  순서가 바뀌어도 (10원 29원, 18원), (20원, 9원, 28원), (20원, 29원, 8원) 형태가 되어서 일정한 금액을 받습니다.  문제의 핵심은 음수를 많이 만들어서 등수에 의해서 빠지는 수를 적게 하는 것입니다.

 

그러면, 정렬을 해서, 적은 금액의 팁을 생각한 것들의 등수를 뒤로 밀어놓음으로써, 가능한 많은 음수를 만드는 것입니다.  예를 들어서 3명의 손님이 1원, 2원, 3원을 생각했다면, 순서대로 받아서 팁을 1원, 1원, 1원 받는 것보다 3원, 1원, 0원을 받는 것이 더 이득이 됩니다.

 

그래서 정렬을 한다음, 등수에 의해서 단순하게 빼주면 됩니다.  등수가 증가하는 수열이 되기 때문에 그 지점이 만나는 곳 이후부터는 사실 의미가 없습니다.  왜냐하면 그 이후에는 생각하는 팁의 액수는 작거나 같은 반면에 등수는 점점 밀려서 빼야되는 수가 커지기때문에 한번 0 이하가 되면, 다음수들은 고려할 필요가 없습니다.

 

제가 작성한 소스입니다.  사실 조건겅사를 매번했지만, 어느수 이후에는 할 필요가 없기 때문에 굳이 이렇게 짤 필요는 없었네요.  참고용으로 보세요.

//------------------------------------------------------
//    baekjoon #1758
//        - by Aubrey Choi
//        - created at 2019-08-29
//------------------------------------------------------
#include <stdio.h>
#include <algorithm>

bool cmp(int a, int b) { return a>b; }
int main()
{
    int n, v[100000];
    long long ans=0;
    scanf("%d", &n);
    for(int i=0;i<n;i++) scanf("%d",v+i);
    std::sort(v,v+n,cmp);
    for(int i=0;i<n;i++) ans+=(v[i]-i>0)?v[i]-i:0;
    printf("%lld\n", ans);
}