[백준 30022] 행사 준비 (C++)

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

30022번: 행사 준비

 

문제

---

동하와 지원이는 ANA 행사를 준비하고 있다. 행사를 위해 N종류의 물건이 한 개씩 필요하기 때문에 동하가 A개를, 지원이가 B개를 나눠서 준비하기로 했다.

근처에 있는 상점 1, 2에서 N종류의 물건을 모두 판매하고 있다. 같은 물건이라도 상점에서 판매하는 가격이 다를 수 있기 때문에 동하는 상점 1에서, 지원이는 상점 2에서 물건을 구입하려고 한다. 상점 1에서는 각각의 물건을 p₁,p₂, ⋯ ,p_N원에 판매하고, 상점 2에서는 q₁,q₂, ⋯q_N원에 판매한다.

동하가 상점 1에서 A개의 물건을, 지원이가 상점 2에서 B개의 물건을 구입해서 N종류의 물건을 모두 구매하는 데 필요한 최소 비용을 구해보자.

 

입력

---

첫째 줄에 정수 N(2 ≤ N ≤ 100,000)과 정수 A,B(1 ≤ A,B ≤ N; A+B=N)가 공백으로 구분되어 주어진다.

둘째 줄부터 N개의 줄에 정수 p_i, p_q(1 ≤ p_i, p_q ≤ 10⁹)가 공백으로 구분되어 주어진다. pi,qi는 상점 1, 2에서 i번째 물건을 판매하는 가격을 의미한다.

 

출력

---

상점 1에서 A개의 물건을, 상점 2에서 B개의 물건을 구입해서 N종류의 물건을 모두 구매하는 데 필요한 최소 비용을 출력한다.

 

문제 풀이

---

상점 1에서 상점 2보다 싸게 파는 것들을 산 후, 상점 2에서 나머지 물건을 사면 된다. 상점 1에서 A개를 사고, 상점 2에서 B개를 사야하므로, 상점 2에 비해 상점 1이 싸게 파는 순으로 정렬한 후 상점 1, 2에서 각각 A개, B개를 사면 최소 비용이 된다.

 

아래는 코드.

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

bool cmp(pair<int, int>& p1, pair<int, int>& p2)
{
	int diff1 = p1.second - p1.first;
	int diff2 = p2.second - p2.first;
	if (diff1 > diff2)
	{
		return true;
	}
	else
	{
		return false;
	}
}

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

	int N, A, B;
	int p, q;
	cin >> N >> A >> B;
	pair<int, int>* arr = new pair<int, int>[N];
	long long answer = 0;
	for (int i = 0; i < N; i++)
	{
		cin >> p >> q;
		arr[i] = make_pair(p, q);
	}
	sort(arr, arr + N, cmp);
	for (int i = 0; i < A; i++)
	{
		answer += arr[i].first;
	}
	for (int i = A; i < N;i++)
	{
		answer += arr[i].second;
	}
	cout << answer << "\n";
	return 0;
}