백준 15720번: 카우버거 (C++)

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

15720번: 카우버거

---

Solved By: Greedy Algorithm

 

세트가 만들어질 수 있는 최대의 개수를 minv라고 하겠습니다. 버거에서 minv개까지 내림차순으로 비용에 0.9를 곱합니다.

 

왜냐하면 세트로 만들었을 때, 어떠한 경우에도 다른 값에 할인을 했다가는 최솟값을 가질 수 없기 때문에 가장 큰 값에 0.9를 곱하여 다 더해주는 것이 맞습니다. => 그리디 알고리즘인 이유

 

버거와 음료, 사이드 모두 마찬가지이기 때문에 같은 과정을 거칩니다.

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

int b, c, d;
vector<int> B, C, D;

bool cmp(int a, int b) {return a > b;}

int main(){
    cin >> b >> c >> d;
    int minv = min(min(b, c), d);
    
    int sum = 0;
    
    for(int i = 0; i < b; i++){
        int v; cin >> v; B.push_back(v);
        sum += v;
    }
    for(int i = 0; i < c; i++){
        int v; cin >> v; C.push_back(v);
        sum += v;
    }
    for(int i = 0; i < d; i++){
        int v; cin >> v; D.push_back(v);
        sum += v;
    }
    
    sort(B.begin(), B.end(), cmp);
    sort(C.begin(), C.end(), cmp);
    sort(D.begin(), D.end(), cmp);
    
    for(int i = 0; i < minv; i++){
        B[i] *= 0.9;
        C[i] *= 0.9;
        D[i] *= 0.9;
    }
    
    int sum2 = 0;
    for(int i = 0; i < b; i++) sum2 += B[i];
    for(int i = 0; i < c; i++) sum2 += C[i];
    for(int i = 0; i < d; i++) sum2 += D[i];
    
    cout << sum << '\n' << sum2;
    return 0;
}