[백준 25947] 선물할인 (C++)

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

문제

---

 n개의 선물 가격이 주어졌을 때, b의 예산으로 최대로 많은 선물을 사려고 한다. 이때 최대 a개의 선물에 대해서는 반값 할인을 받을 수 있다고 했을 때 최대로 살 수 있는 선물의 수를 구하는 프로그램을 작성하시오. 단, 한 선물에는 최대 한 번만 반값 할인을 받을 수 있다.

 

입력

---

입력은 표준입력을 사용한다. 첫 번째 줄에 선물의 개수를 나타내는 양의 정수 n (1 ≤ n ≤ 100000), 예산을 나타내는 양의 정수 b (1≤b≤109), 반값 할인을 받을 수 있는 최대 선물의 수를 나타내는 정수 a (0 ≤ a ≤ n)가 공백을 사이에 두고 차례로 주어진다. 다음 줄에 n개의 선물 가격이 공백을 사이에 두고 주어진다. 선물 가격은 2이상 10억 이하의 값을 갖으며, 항상 짝수로 주어진다.

 

출력

---

출력은 표준출력을 사용한다. 조건을 만족하며 최대로 살 수 있는 선물의 수를 출력한다.

 

문제 풀이

---

그리디 + 누적합 문제.

 

반값할인 a개를 포함하여 최대한 싸게 구입하려면 가장 비싼 것 a개를 반값 할인 받으면 된다. 예산이 정해져 있으므로, 해당 예산에서 살 수 있는 것 중 가장 비싸게 살 수 있는 a개를 선택하여 반값 할인 받고, 나머지는 정가로 구매하면 된다. 오름차순 정렬한 후 i번째 선물까지의 합을 구하면 i개를 살 수 있는 최대의 예산을 구할 수 있다. 위에서 설명한대로 i개 중 비싼 a개는 반값 할인을 적용해주면 된다.

 

반값 할인까지 적용하여 i번째 선물까지의 합을 저장하는 배열 halfSaleSum은 항상 그 값이 증가한다. 따라서 upper_bound()를 이용하면 iterator를 얻어올 수 있는데, 이 iterator는 예산을 초과하는 첫번째 원소를 가리키고 있으므로 1을 빼주면 정답이 된다.

 

아래는 코드.

#include <iostream>
#include <algorithm>
using namespace std;

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

	int N, b, a;
	cin >> N>>b>>a;
	int* arr = new int[N];
	long long* originalSum = new long long[N + 1];
	long long* halfSaleSum = new long long[N + 1];
	for (int i = 0; i < N; i++)
	{
		cin >> arr[i];
	}
	sort(arr, arr + N);
	originalSum[0] = 0;
	halfSaleSum[0] = 0;
	for (int i = 1; i <= N; i++)
	{
		originalSum[i] = originalSum[i - 1] + arr[i - 1];
	}
	for (int i = 1; i <= N; i++)
	{
		if (i <= a)
		{
			halfSaleSum[i] = originalSum[i] / 2;
		}
		else
		{
			long long halfSale = originalSum[i] - originalSum[i - a];
			halfSaleSum[i] = originalSum[i - a] + halfSale / 2;
		}
	}
	cout << upper_bound(halfSaleSum, halfSaleSum + N + 1, b) - halfSaleSum - 1<<"\n";
	return 0;
}