[백준] 11256번 사탕 (그리디 알고리즘)

-문제

 

-코드

#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;

int main() 
{
	int t, j, n, r, c, res = 0;
	scanf("%d", &t);
	vector<int> a;

	for (int i = 0; i < t; i++)
	{
		scanf("%d %d", &j, &n);
		a.clear();
		res = 0;

		for (int i = 0; i < n; i++)
		{
			scanf("%d %d", &r, &c);
			a.push_back(r*c);
		}

		sort(a.rbegin(), a.rend());

		for (int i = 0; i < n; i++)
		{
			j -= a[i];
			res++;
			if (j <= 0) break;
		}

		printf("%d\n", res);

	}


	return 0;
}