[백준 25045] 비즈마켓 (C++)

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

25045번: 비즈마켓

문제

---

 

비즈마켓은 "고객 기업 운영의 효율화에 기여하며, 그 구성원의 복지 만세를 추구한다." 라는 기조 아래 기업을 주 대상으로 복지몰 사업, 기업 판촉 및 사은품 사업, 산업재 유통 사업을 하는 온라인 종합상사입니다. 이 주 사업 분야 외에도 비즈마켓은 브랜드 사업, 렌탈 사업, 에너지 사업 등 다양한 분야에서 사업을 진행하고 있습니다. 오늘 신욱이는 비즈마켓으로부터 효율적으로 렌탈 사업을 운영하는 것을 도와달라는 의뢰를 받았습니다.

비즈마켓에는 N개의 물품이 있고, 물품을 렌탈하기를 원하는 M개의 고객 기업이 있습니다. 각 물품은 A 의 만족도를 가지고 있으며, 각 고객 기업은 B_j 의 비용을 지불하여 렌탈을 진행하고자 합니다. 각 고객 기업은 하나의 물품만 렌탈할 수 있으며, 각 물품 또한 하나의 고객 기업에만 렌탈해줄 수 있습니다.

 A_i 의 만족도를 가지는 물품을 B_j 의 비용을 지불하고자 하는 고객 기업에 렌탈해주게 되면 A_i - B_j 만큼의 고객 만족도를 얻을 수 있습니다. 모든 고객 기업들은 적어도 자신이 지불한 비용만큼의 만족도를 얻기를 원하기 때문에, 고객 만족도가 0보다 작아진다면 거래를 진행하지 않을 것입니다. 거래를 진행하지 않으면 당연히 고객 만족도도 얻을 수 없습니다.

신욱이가 구체적으로 해야 하는 일은 각 고객 기업에 렌탈해 줄 물품을 잘 정해서 고객 만족도의 합을 최대로 만드는 것입니다. 하지만 신욱이는 해야 할 과제가 너무 많았던 나머지, 이 일을 여러분들한테 넘기고 과제를 하러 떠나버렸습니다. 신욱이를 대신해 고객 만족도의 합의 최댓값을 구해줍시다.

입력

---

첫 번째 줄에는 상품의 수를 의미하는 정수 N과 고객 기업의 수를 의미하는 정수 M이 공백으로 구분되어 주어집니다. (1 ≤ N, M ≤ 2×10⁵)

두 번째 줄에는 각 상품의 만족도 A₁, A₂, A₃, … , A_N을 의미하는 정수 N개가 공백으로 구분되어 주어집니다. (0 ≤ A_i ≤ 10⁹)

세 번째 줄에는 고객 기업이 지불하고자 하는 비용 B₁, B₂, B₃, … , B_M을 의미하는 정수 M개가 공백으로 구분되어 주어집니다. (0 ≤ B_i ≤ 10⁹)

 

출력

---

첫 번째 줄에 각 고객 기업에 대여해 줄 물품을 잘 골라서 얻을 수 있는 고객 만족도의 합의 최댓값을 출력합니다.

 

 

문제 풀이

---

그리디 문제.

고객 만족도가 가장 낮은 기업에게 만족도가 가장 높은 상품을 대여해주면 그 차이가 가장 큰 값이 되므로 해당 방법으로 반복문을 돌려 모든 고객 기업에게 물품을 대여해주면 된다. 고객 기업의 수보다 상품의 수가 더 적다면 모든 기업에게 대여해줄 수 없다. 고객 만족도가 낮은 기업 순으로 N개의 기업에게 차례대로 대여할 수 있는 상품들(다른 기업에게 대여받지 않은 상품들) 중 가장 만족도가 높은 상품을 대여해준다.

 

아래는 코드.

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

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

	int N, M;
	cin >> N >> M;
	long long* products = new long long[N];
	long long* companies = new long long[M];
	long long answer = 0;
	for (int i = 0; i < N; i++)
	{
		cin >> products[i];
	}
	for (int i = 0; i < M; i++)
	{
		cin >> companies[i];
	}
	sort(products, products + N);
	sort(companies, companies + M);
	for (int i = 0; i < min(M , N) ; i++)
	{
		if (products[N - 1 - i] - companies[i] >= 0)
		{
			answer += products[N - 1 - i] - companies[i];
		}
	}
	cout << answer << "\n";
	return 0;
}