[BOJ] 11256번 사탕

풀이

최대한 적은 숫자의 상자를 이용하여 조건을 만족시키는 전형적인 그리디 알고리즘 문제였습니다. 입력값으로 상자의 가로 세로 크기가 주어졌기에, 이를 각각 저장하기 보다는 담을 수 있는 사탕의 개수로 한 번에 저장해 주었습니다.
이렇게 값들을 저장해 준 이후, 정렬을 통해 조건을 만족시키는 답을 구하였습니다.

코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void init() {
	ios::sync_with_stdio(false);
	cin.tie(0);
}

int main() {
	init();
	
	vector<int> v;	// 사탕을 담을 수 있는 상자의 개수 저장
	int test;	// 테스트 케이스 개수 저장
	int J, N; // 사탕의 개수:J, 상자의 개수:5
	int ans, index;

	cin >> test;
	for (int i = 0; i < test; i++) {
		cin >> J >> N;
		for (int j = 0; j < N; j++) {
			// 상자의 가로 세로값을 입력받음
			int tempR, tempC;
			cin >> tempR >> tempC;

			// 상자에 저장 가능한 사탕의 개수로 한번에 저장
			v.push_back(tempR * tempC);
		}
		sort(v.begin(), v.end());

		ans = 0; index = 0;
		for (int k = 0; k < v.size(); k++) {
			if (ans >= J) break;
			ans += v.back();
			v.pop_back();
			index += 1;
		}
		cout << index << endl;

		v.clear();
	}

	return 0;
}

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