[C++] BOJ 25405: 레벨 업

2026년 2월 26일

대충 오름차순 정렬해서 앞에 $$K$$ 개 원소를 $$1$$ 씩 올리는 걸 $$M$$ 번 반복한 뒤에 나오는 결과 배열을 출력하면 된다.
총합 원래 수열에서 $M \times K$ 만큼 수가 추가되고, 하나의 원소는 최대 $$M$$ 번만 $$1$$ 씩 올라갈 수 있다.

상한선 $$T$$ 를 찾아보자. 우리의 목표는 수들을 $$T$$ 까지 올리는 것이다.
단, 하나의 원소는 최대 $$M$$ 만큼 추가될 수 있다. 따라서 한 원소의 $$T$$ 까지 (만약 $L_{i} + M < T$ 라면, $L_{i} + M$ 까지) 올리는 데에 필요한 비용은 $\min\left(M, \max\left(0, T - L_{i}\right)\right)$ 가 된다.
이 비용의 합이 $M \times K$ 만 안넘어가면 $$T$$ 로 수의 상한선을 잡을 수 있다.

이분 탐색을 돌리자. $\mathcal{O}(N \log{N})$ 의 시간복잡도로 $$T$$ 를 찾을 수 있다.
$$T$$ 를 찾은 뒤에 수열 $$L$$ 을 잘 업데이트해주고, 남은 수들은 $L_{i} = T$ 인 친구들에게 적절히 분배해주면 된다.

c++

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#define endl '\n'
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second

using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
using lll = __int128_t;
using ulll = __uint128_t;

const int INF = 1'000'000'007;
const ll LINF = 1'000'000'000'000'000'007;

int N, K;
vector <ll> L;
ll M;

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

    cin >> N;

    L.resize(N);
    for(int i = 0; i < N; i++) {
        cin >> L[i];
    }
    
    cin >> M >> K;

    sort(all(L));

    auto f = [&](ll mid) -> unsigned char {
        ll tot = 0;
        for(int i = 0; i < N; i++) {
            tot += min(M, max(0LL, mid - L[i]));
        }
        return (tot <= M * K ? 1 : 0);
    };

    ll s = 0, e = LINF;
    ll ans = 0;
    while(s <= e) {
        ll mid = (s + e) >> 1;
        if(f(mid) == 1) {
            s = mid + 1;
            ans = mid;
        }
        else {
            e = mid - 1;
        }
    }

    ll use = M * K;
    for(int i = 0; i < N; i++) {
        ll to_use = min(M, max(0LL, ans - L[i]));
        L[i] += to_use;
        use -= to_use;
    }

    for(int i = 0; i < N && use > 0; i++) {
        if(L[i] == ans) L[i]++, use--;
    }

    sort(all(L));
    for(ll &x : L) cout << x << " ";
    cout << endl;
    return 0;
}