백준 11256번: 사탕 (C++)

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

---

Solved By: Greedy Algorithm

 

상자를 최대한 적게 쓸려면 사이즈가 큰 순서대로 상자를 쓰면 된다. => 그리디 알고리즘인 이유

상자의 사이즈 크기 순서대로 배열을 정렬하고,

사탕의 개수에서 상자의 크기를 하나씩 빼가면서 다 뺐을 경우, 몇 개까지 상자를 사용했는지 저장하여 출력했다.

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

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

int main(){
    int T; cin >> T;
    vector<int> res;
    while(T--){
        int n, m; cin >> n >> m;
        vector<int> v;
        
        for(int i = 0; i < m; i++){
            int r, c; cin >> r >> c;
            v.push_back(r * c);
        }
        
        sort(v.begin(), v.end(), cmp);
        
        int cnt = 0;
        
        for(int i = 0; i < v.size(); i++){
            n -= v[i];
            if(n <= 0){
                res.push_back(i + 1);
                break;
            }
        }
    }
    
    for(auto v : res) cout << v << '\n';
}