[Silver V] 사탕 - 11256

[문제 위치]

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

[문제 풀이]

그리디 알고리즘 문제이다.

먼저 테스트 케이스의 개수 T를 입력받는다.

 

각 테스트 케이스마다 사탕의 개수 J와 상자의 개수 N을 입력받는다. 이후 N개의 줄에 걸쳐 각 상자의 세로 길이 R과 가로 길이 C를 입력받고, 상자의 용량 R×C를 계산하여 벡터 box_sizes에 저장한다. box_sizes를 내림차순으로 정렬한다.

 

이는 박스의 개수를 최소화해야하므로 하나의 박스에 최대한 많은 사탕을 담기 위해서이다.

 

정렬된 순서대로 상자를 하나씩 사용하며 J에서 해당 상자의 용량을 빼고, 사용할 때마다 box_count를 1씩 증가시킨다.

 

J가 0 이하가 되면 반복을 멈추고 box_count를 출력한다. 이 과정을 모든 테스트 케이스에 대해 반복한다.

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

using namespace std;

int main() {
    int T;
    cin >> T;

    while (T--) {
        int J, N;
        cin >> J >> N;

        vector<int> box_sizes(N);
        for (int i = 0; i < N; i++) {
            int R, C;
            cin >> R >> C;
            box_sizes[i] = R * C;
        }

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

        int box_count = 0;
        for (int i = 0; i < N; i++) {
            J -= box_sizes[i];
            box_count++;
            if (J <= 0) break;
        }

        cout << box_count << endl;
    }

    return 0;
}