백준 1092 배 (C++)

1092번: 배

그리디를 이용한 문제이다. 먼저 입력받은 크레인과 박스 무게들을 내림차순으로 정렬을 해주었다. 그리고 박스의 크기만큼 반복문을 돌면서 크레인 각각의 무게 제한과 비교하는 반복문을 통해 크레인이 옮길 수 있을 경우 박스를 erase하여 제거해주고 이를 반복해주었다. 최종적으로 박스를 모두 옮긴다면 box 벡터에는 아무것도 남지 않게 된다. 마무리 후 result를 출력해주었다. 만약 남아있다면 옮길 수 없는 박스가 존재하는 것이므로 -1을 출력해주었다. 어렵지 않게 풀 수 있었던 문제였다. 그리디에 슬슬 익숙해지고 있는 것 같다.

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

using namespace std;

int N, M, result = 0;
vector<int> crane;
vector<int> box;

void solution() {
    sort(crane.rbegin(), crane.rend());
    sort(box.rbegin(), box.rend());

    for (int i = 0; i < box.size(); i++) {
        if (box.empty()) break;

        bool tf = false;
        int next = i;
        for (int j = 0; j < crane.size(); j++) {
            if (next >= box.size()) break;

            if (box[next] <= crane[j]) {
                tf = true;
                box.erase(box.begin() + next);
            }
            else {
                j--;
                next++;
            }
        }

        if (tf) {
            i--;
            result++;
        }
    }

    if (!box.empty()) result = -1;

    cout << result;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> N;
    
    int a;
    for (int i = 0; i < N; i++) {
        cin >> a;
        crane.push_back(a);
    }

    cin >> M;

    for (int i = 0; i < M; i++) {
        cin >> a;
        box.push_back(a);
    }

    solution();

    return 0;
}