[백준(BOJ)] 선물할인(25947번)_C++

문제를 보고 러프하게 풀이방법을 생각해보면 브루트포스가 있다.

하지만, O(n^2)이라 시간초과가 날 것이다.

 

그러면 O(n) 혹은 O(nlogn) 정도의 로직으로 코드를 구성해야 한다.

 

최대 a개 만큼 반값할인을 받을 수 있다고 문제에 나와 있다.

10개 중에 최대 3개를 할인받을 수 있다고 가정해보면

해당 10개를 모두 구매할 수 있든 없든 항상 상위 3개를 할인받는 것이 가장 유리하다.

 

따라서 우리는 하위 a개를 고려할 필요없이 상위 a개의 반값할인만을 고려하면 된다.

 

 

이 문제를 풀기 위해서 우리는 매번 임의의 개수의 선물의 가격의 합을 구해야한다.

이 작업만 해도 O(n)이기 때문에 누적합을 이용해서 이를 선처리해줄 것이다.

 

위의 굵은 글씨에 해당하는 두가지를 사용하려면

선물들의 가격순으로 오름차순 정렬하는 것이 필수다.

 

일반적인 누적합만을 이용해서는 이 문제를 해결하기 힘들다.

반값할인이 얼마나 가능할지도 계산해야 하는데 이또한 O(n)이기 때문이다.

따라서 반값할인에 대한 것도 누적합을 사용하면 된다.

(오름차순 정렬하고, 상위 a개만 반값할인을 고려해도 되기 때문)

 

우리가 한가지 명심해야할 것은 최대 a개 만큼 반값할인을 받을 수 있다는 것이다.

즉, a개 이하의 개수만큼만 반값할인을 받을 수도 있다.

물론 항상 상위 a개를 할인받는 것이 유리하지만, 구매할 수 있는 최대 개수가 a보다 작을 수도 있으므로

이에 대한 예외처리도 해주어야 한다.

 

---

정답코드

#include <iostream>
#include <algorithm>

using namespace std;

int n, b, a;
int price[100'001];
long long sum[100'001], half[100'001];

int main(){
    cin.tie(NULL);
    cout.tie(NULL);
    ios_base::sync_with_stdio(false);

    cin >> n >> b >> a;
    for (int i = 1; i <= n; i++)
        cin >> price[i];

    sort(price, price + n + 1);
    
    sum[1] = price[1];
    half[1] = price[1] / 2;
    for (int i = 2; i <= n; i++) {
        sum[i] = sum[i - 1] + price[i];
        half[i] = half[i - 1] + price[i] / 2;
    }

    for (int i = n; i > 0; i--) {
        if (sum[i] - (half[i] - half[i - a > 0 ? i - a : 0]) <= b) {
            cout << i << "\n";
            return 0;
        }
    }

    cout << 0 << "\n";

    return 0;
}