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

 

풀이

• 상자를 높이와 너비순으로 정렬한다. -> 큰 상자부터 사용할 수 있어서 최소한의 상자를 사용할 가능성이 높아진다.
• 각 상자를 순서대로 확인하면서 해당 상자에 사탕을 담을 수 있는지 확인한다. 담을 수 있는 경우에는 해당 상자에 담고 candlesLeft에서 담은 사탕의 개수를 뺀다.
• 모든 상자를 확인하면서 담은 후, usedBoxes에는 사용한 상자의 개수가 저장된다.
• 마지막으로 useBoxes를 출력하여 최소한의 상자 개수를 표시한다. 

 

 

코드

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

using namespace std;

struct Box {
    int height;
    int width;
};

bool compareBoxes(const Box &a, const Box &b) {
    return a.height * a.width > b.height * b.width;
}

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

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

        vector<Box> boxes(N);

        for (int i = 0; i < N; i++) {
            cin >> boxes[i].height >> boxes[i].width;
        }

        sort(boxes.begin(), boxes.end(), compareBoxes);

        int usedBoxes = 0;
        int candiesLeft = J;

        for (int i = 0; i < N && candiesLeft > 0; i++) {
            int candiesInBox = min(candiesLeft, boxes[i].height * boxes[i].width);
            candiesLeft -= candiesInBox;
            usedBoxes++;
        }

        cout << usedBoxes << endl;
    }

    return 0;
}

 

 

 

 

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

11256번: 사탕