Koala - 11기/코딩테스트 준비 스터디

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

_dudu 2023. 9. 2. 19:06

 

풀이

  • 상자를 높이와 너비순으로 정렬한다. -> 큰 상자부터 사용할 수 있어서 최소한의 상자를 사용할 가능성이 높아진다.
  • 각 상자를 순서대로 확인하면서 해당 상자에 사탕을 담을 수 있는지 확인한다. 담을 수 있는 경우에는 해당 상자에 담고 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번: 사탕

당신은 사탕 공장의 주인이다. 날마다, 당신은 J개의 사탕을 가게에 보내기 위해 상자에 포장해야 한다. 당신은 크기가 다른 상자 N개를 가지고 있다. 당신은 편리를 위해 상자를 최소한으로 쓰

www.acmicpc.net