[C++] 백준 11256번: 사탕

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

11256번: 사탕

1. 문제풀이

 그리디 알고리즘을 이용한 문제로, 상자를 최소한으로 사용하기 위해서 크기가 큰 상자부터 사탕을 담으면 된다. 입력받은 상자의 정보를 바탕으로 상자의 크기를 우선순위 큐에 저장하고, 사탕의 개수가 0이하가 될 때까지 반복문을 돌면서 우선순위가 높은 원소를 꺼내면서 상자의 개수를 1씩 증가시킨다.

 2. C++ 코드

#include <iostream>
#include <queue>

using namespace std;

int main()
{
    int t, j, n, r, c, cnt;
    scanf("%d", &t);
    while (t--) {
        priority_queue<int> pq;
        cnt = 0;
        scanf("%d %d", &j, &n);
        for (int i = 0; i < n; i++) {
            scanf("%d %d", &r, &c);
            pq.push(r * c);
        }
        while (!pq.empty()) {
            j -= pq.top();
            pq.pop();
            cnt++;
            if (j <= 0) {
                break;
            }
        }
        printf("%d\n", cnt);
    }

    return 0;
}