백준 1092: 배

문제 요약

지민이는 항구에서 일한다. 그리고 화물을 배에 실어야 한다. 모든 화물은 박스에 안에 넣어져 있다. 항구에는 크레인이 N대 있고, 1분에 박스를 하나씩 배에 실을 수 있다. 모든 크레인은 동시에 움직인다.

각 크레인은 무게 제한이 있다. 이 무게 제한보다 무거운 박스는 크레인으로 움직일 수 없다. 모든 박스를 배로 옮기는데 드는 시간의 최솟값을 구하는 프로그램을 작성하시오.

문제 분류

• 그리디 알고리즘
• 정렬

문제 풀이

정렬하여 순회하면서 카운팅하면 되는 그리디 알고리즘이다. 크레인은 set으로, 박스는 vector로 넣어서 각각 내림차순 정렬시켰다.

그 이후 각 크레인에 대해서 박스의 무게가 크레인보다 작거나 같은 경우에 매칭시킨다. 모든 크레인을 순회하였거나 모든 화물을 순회한 경우에는 크레인을 움직이면 된다(res++). 그리고 크레인을 처음부터 다시 매칭시키며(iter = s.begin()), 박스도 처음부터 비교하여야 한다(in = 0).

이미 옮겨진 박스는 0을 대입시켜서 0이 아닌 경우에만 옮기도록 하고, 크레인 혹은 화물의 순회 종료 시 모든 화물을 옮겼을 경우에 그 횟수를 출력해주었다.

화물의 무게가 크레인의 최대값보다 크게 입력되었을 경우 곧바로 -1을 출력하고 프로그램을 종료한다.

풀이 코드

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>

using namespace std;

int main() {
    int n, m, in, res = 1, cnt = 0;
    multiset<int, greater<int>> s;
    vector<int> v;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &in);
        s.insert(in);
    }
    scanf("%d", &m);
    for (int i = 0; i < m; i++) {
        scanf("%d", &in);
        if (in > *s.begin()) {
            cout << -1;
            return 0;
        }
        v.push_back(in);
    }
    sort(v.begin(), v.end(), greater<int>());
    auto iter = s.begin();
    in = 0;
    while (1) {
        if (v[in] <= *iter && v[in]) {
            v[in] = 0;
            iter++;
            cnt++;
        }
        in++;
        if (in >= m || iter == s.end()) {
            if (cnt == m) break;
            in = 0;
            res++;
            iter = s.begin();
        }
    }
    cout << res;
    return 0;
}