[BOJ] 25635 자유 이용권

문제

풀이

코드

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

int n;
ll arr[100001];
int main() {
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) {
        scanf("%lld", &arr[i]);
    }
    sort(arr + 1, arr + n + 1); // 정렬하고
    for(int i = 1; i <= n; i++) { // 누적합 계산
        arr[i] += arr[i-1];
    }

    ll ans = 0; // long long 타입인걸 주의하자
    for(int i = n; i > 0; i--) {
        ll cur = arr[i] - arr[i-1] - 1; // 현재 필요한 개수

        if (cur > arr[i-1] + ans) { // 필요한 개수보다 적으면
            ans += arr[i-1] + ans + 1; // 최대로 할 수 있는 만큼만 더해주고
        } else ans += arr[i] - arr[i-1]; // 아니면 다 해주기
    }

    printf("%lld", ans);
}