[백준 1758번] 알바생 강호 (C++)

문제링크 : https://www.acmicpc.net/problem/1758

1758번: 알바생 강호

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = INT_MAX;

int N, arr[100001];
ll result = 0;

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);

    cin >> N;

    for(int i=1; i<=N; i++) cin >> arr[i];

    sort(arr+1, arr+N+1, greater<>()); 

    for(int i=1; i<=N; i++)
    {
        if(arr[i]-(i-1) < 0) continue; //음수 스킵
        result += (arr[i]-(i-1));
    }

    cout << result;

    return 0;
}

 

값이 최대가 되도록 하기 위해 우선 입력받은 값에 대해 내림차순 정렬을 해준다.

이후 기존 팁 금액에 등수차 금액을 빼고, 해당 값이 음수면 스킵한다.

양수면 무사히 팁을 받았기에 해당 팁을 저장하고 출력해준다.

 

배열의 최대 값이 10만이고, N의 범위도 10만이기에 합하는 과정에서 int 범위를 넘길 수 있으므로 long long으로 선언해주어야 한다.