25947: 선물할인

• toc {:toc}

문제 확인하기

풀이

아무리 봐도 전체적인 로직은 맞는데 계속 틀려서 왜 그런가 하고 봤더니 바보같이 배열의 시작을 1로 두고 sort는 0부터 시작했다. 다시 0으로 전체를 맞춰줬더니 통과했다.

가격이 작은 선물부터 넣기 시작한다. 먼저 할인할 수 있는 개수만큼 할인하면서 총합을 예산과 비교한다. 할인할 수 있는 개수가 끝나도 예산이 초과하지 않는다면 더 살 수 있는 가능성이 있기 때문에 이전에 반값 할인 했던 선물을 제 값을 주고 살 수 있도록 반값을 다시 더해주고, 아직 사지 않은 선물 중 가장 싼 선물을 할인해서 더하고 예산과 비교한다.

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
 
double price[100005];
 
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
 
    long long n, b, a;
    double sum = 0, res = 0;
 
    cin >> n >> b >> a;
 
    for(int i = 0; i < n; i++){
        cin >> price[i];
    }
 
    sort(price, price+n);
 
    for(int i = 0; i < a; i++){
        sum += price[i]/2;
        if(sum > b){
            cout << res << endl;
            exit(0);
        }
        res++;
        if(i == n-1) {
            break;
        }
    }
 
    for(int i = a; i < n; i++){
        sum += price[i-a] / 2;
        sum += price[i] / 2;
        if(sum > b){
            break;
        }
        res++;
    }
 
    cout << res << endl;
 
    return 0;
}