백준 1758 알바생 강호 c++ [컴공과고씨]

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

1758번: 알바생 강호

이 문제를 보고 조금 생각을 해본 결과 팁을 많이 주고 싶어하는 사람들을 앞쪽에 세워야지 가장 많은 팁을 얻을 수 있다. 왜냐하면 뒤로 등수가 밀릴수록 그 만큼 빼주어야한다. 그렇다면 팁을 10을 주고 싶은사람이 10등인것과 팁을 1을 주고싶은 사람이 10등이라면 전자는 0원 후자는 음수가 되어진다. 여기서 음수는 0으로 처리가 되어지기 때문에 둘다 똑같이 못받는 꼴이 된다. 그러나 둘다 9등일경우 10원을 주고 싶은 사람에게 팁을 1원을 받을 수 있지만 후자는 똑같이 음수가 된다. 즉, 팁을 많이 주고 싶은 사람을 앞쪽으로 옮기는 것이 항상 팁을 많이 받을 수 있는 경우가 된다.

그래서 각 팁을 주고 싶은 수를 내림차순으로 정렬 후 팁에서 자기 등수를 빼 음수보다 크다면 팁 합계에 더해주면된다.

 

sort할때는 알고리즘 라이브러리에 있는 sort를 사용하여 sort(배열, 배열 + n, cmp)를 사용했다.

여기서 cmp는 내림차순으로 정렬할때 greater<자료형>()을 사용해도 되고 자신이 cmp 비교함수를 구현해서 내림차순으로 만들어주어도 되는데 나는 cmp를 만들어서 넣어주었다. 

 

전체코드

#include <iostream>
#include <algorithm>
using namespace std;
bool cmp(long long a, long long b){
    return a > b;
} // 내림차순 cmp 구현
 
int main(){
    long long tips[100001];
    int n;
    cin >> n;
    for (int i = 0; i < n;i++){
        cin >> tips[i];
    }
    sort(tips, tips + n, cmp); // 오름차순으로 정렬 greater<long long>() 사용해도 무방
    long long sum = 0;
    for (int i = 0; i < n;i++){
        if(tips[i] - i > 0){ // 팁 - 등수가 양수
            sum += tips[i] - i; //합계에 더해줌
        }
    }
    cout << sum;
    return 0;
}

사용 알고리즘 : sort

 

yea!