(C++) 백준 1092.배

백준 1092번 배(C++)

---

문제 설명:

• 최대로 옮길 수 있는 무게가 제한되어있는 크레인이 주어지고 옮겨야 할 박스의 무게들이 주어진다.
  각 크레인은 동시에 박스를 하나씩 옮길 수 있고 모든 박스를 옮기는데에 걸리는 시간을 출력해야한다.
  모든 박스를 옮길 수 없는 경우 -1을 출력한다.

---

문제 풀이:

• 각 크레인은 남겨진 박스들 중에 옮길 수 있는 가장 무거운 박스들을 선택해서 하나씩 선택하고 동시에 옮긴다.
  • 크레인과 박스를 벡터에 각각 저장하고 두 벡터를 내림차순 정렬한다.
    • 스택(stack)을 이용하여 옮기지 못하는 박스는 다시 우선적으로 옮기도록 한다.
• 모든 박스를 옮길 수 없는 경우
  • 가장 힘이 센 크레인이 옮길 수 없는 박스가 존재하는 경우.

---

코드

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
#define FOR(i,N) for(int i=1; i<=N; i++)
int N,M;
vector<int> cranes;
vector<int> boxes;
int ans=0;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> N;
    FOR(i,N) {
        int x; cin >> x;
        cranes.push_back(x);
    }
    cin >> M;
    FOR(i,M) {
        int x; cin >> x;
        boxes.push_back(x);
    }
    sort(cranes.rbegin(), cranes.rend());
    sort(boxes.begin(), boxes.end());
    if(*prev(boxes.end())>cranes[0]) {
        cout << -1 << '\n';
        return 0;
    }
    stack<int> extraBoxes;
    stack<int> priorBoxes;
    for(auto& box: boxes) extraBoxes.push(box);
    while(!extraBoxes.empty()) {
        for(auto& crane: cranes) {
            while(!extraBoxes.empty() && extraBoxes.top() > crane) {
                priorBoxes.push(extraBoxes.top());
                extraBoxes.pop();
            }
            if(!extraBoxes.empty())extraBoxes.pop();
        }
        while(!priorBoxes.empty()) {
            extraBoxes.push(priorBoxes.top());
            priorBoxes.pop();
        }
        ans++;
    }
    cout << ans << '\n';
    return 0;
}