[BOJ/Silver 2] 백준 30022 행사 준비(C++)

문제 링크

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

30022번: 행사 준비

 

문제

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

근처에 있는 상점 1, 2에서 N종류의 물건을 모두 판매하고 있다. 같은 물건이라도 상점에서 판매하는 가격이 다를 수 있기 때문에 동하는 상점 1에서, 지원이는 상점 2에서 물건을 구입하려고 한다. 상점 1에서는 각각의 물건을 p1, p2, ⋯, pN원에 판매하고, 상점 2에서는 q1, q2, ⋯, qN원에 판매한다.

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

 

입력

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

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

 

출력

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

 

예제 입력 1

5 2 3
4 6
7 2
5 5
3 6
10 9

예제 출력 1

23

예제 입력 2

2 1 1
2 1
3 4

예제 출력 2

4

 

알고리즘 분류

• 그리디 알고리즘

 

풀이

다른 상점에서 구매할 때보다 지금 상점에서 구매할 때 최대한 가격이 낮아야 한다. 따라서 상점 1에서의 가격과 상점 2에서의 가격 차가 낮은 순으로 N개의 물건을 정렬한다.

그리고 첫 번째 물건부터 A개의 물건을 동하가 구매하고, 나머지 물건은 지원이가 구매한다.

 

코드

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#define LL long long
#define FASTIO cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);

using namespace std;
int N, A, B;
vector<pair<LL, LL> > Vec;
LL Answer;

void input() {
    cin >> N >> A >> B;
    Vec.resize(N);
    for (int i = 0; i < N; i++) {
        cin >> Vec[i].first >> Vec[i].second;
    }
}

bool Comp(pair<LL, LL> PA, pair<LL, LL> PB) {
    return ((PA.first - PA.second) < (PB.first - PB.second));
}

void settings() {
    sort(Vec.begin(), Vec.end(), Comp);
    for (int i = 0; i < A; i++) {
        Answer += Vec[i].first;
    }
    for (int i = A; i < N; i++) {
        Answer += Vec[i].second;
    }
}

void find_Answer() {
    cout << Answer << "\n";
}

int main() {
    FASTIO
    input();
    settings();
    find_Answer();

    return 0;
}