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

유형: 그리디

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

11256번: 사탕

 

풀이

상자는 최대 가로*세로의 개수만큼 사탕을 담을 수 있다.

가로*세로 값을 벡터에 저장한 뒤, 내림차순으로 정렬한다.

그리고 벡터 원소를 하나씩 돌면서(가장 큰 값부터 보게 된다) 전체 사탕 개수 -= 원소값 으로 갱신한다.

이때 사탕 개수가 0 이하가 된다면 사탕을 전부 담게된다.

 

#include "iostream"
#include "vector"
#include "algorithm"

using namespace std;

int solution(vector<int> arr, int total){
    int cnt = 0;

    sort(arr.begin(), arr.end(), greater<>());

    for(auto now: arr){
        total -= now;
        cnt ++;
        if(total <= 0) break;
    }

    return cnt;
}

int main(){
    ios::sync_with_stdio(0);
    int test; cin >> test;

    while(test--){
        int total, box; cin >> total >> box;
        vector<int> arr;

        for(int i = 0; i < box; i++){
            int x, y; cin >> x >> y;
            arr.push_back(x*y);
        }

        cout << solution(arr, total) << endl;
    }

    return 0;
}