[백준/c++] BOJ 25947 - 선물 할인

https://www.acmicpc.net/problem/25947

25947번: 선물할인

 

문제 설명

n개의 선물 가격이 주어지고, b의 예산으로 최대한 많은 선물을 산다. 이때 최대 a개의 선물은 단 한번만 반값 할인을 받을 수 있다. 최대로 살 수 있는 선물의 수를 구하라.

(1 <= n <= 100 000, 1 <= b <= 1000 000 000, 0 <= a <= n) 

 

해결

최대한 많은 선물을 사기 위해서는 적은 가격의 선물들을 사야 한다. 또한, 큰 가격의 선물들에게 반값 할인을 적용해야 한다.

간단히 순서를 접근 순서를 나열해 보면 다음과 같다.

제일 작은 가격의 선물부터 선물 사기 -> 더 이상 살 수 없다면 사려는 선물부터 내려가면서 반값 할인 적용 -> 더 이상 선물을 살 수 없을 때까지 반복

 

코드

#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;

int arr[100005], n, b, a;
int ck_[100005];
int main() {
	int answer = 0;
	long long sum = 0;
	cin >> n >> b >> a;
	for (int i = 0; i < n; i++)
		cin >> arr[i];
	sort(arr, arr + n);

	for (int i = 0; i < n; i++) {
		sum += arr[i];
		if (b >= sum) {
			answer = i + 1;
		}
		else {
			int ck = 0;
			for (int j = i; j >= 0; j--) {
				if (ck_[j]) continue;
				if (!a) break;
				sum -= arr[j] / 2;
				a--;
				ck_[j] = 1;
				if (b >= sum) {
					ck = 1;
					break;
				}
			}
			if (ck) answer = i + 1;
			else break;
		}
	}
	cout << answer;
}