[1일 1알고] G5 1092 배

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

 

입력으로 주어지는 각 크레인에 화물을 적절히 분배하는 것이 문제입니다.

크레인은 무게 하중이 제한되어있기 때문에 이 조건을 지켜야합니다.

---

저는 적절히 분배하기 위해 화물과 크레인의 무게 제한을 역순으로 정렬하고 이를 통해 분배하는 방법을 생각했습니다.

    for (int i = 0; i < M; ++i) //weights
    {
        for (int j = 0; j < N; ++j)//cranes
        {
            if (j == N - 1 || cranes[j + 1] < weights[i] || cnts[j+1] > cnts[j])
            {
                ++cnts[j];
                break;
            }
        }
    }

만약 현재 크레인이 마지막 크레인이거나, 다음 크레인(무게 제한이 더 심한)이 현재 화물의 무게를 수용할 수 없거나, 다음 크레인이 현재 보유하는 물류가 현재 크레인보다 많다면 현재 크레인에 화물을 추가합니다.

 

무거운 물류부터 비교하기 때문에 조건이 적절할 것이라고 생각했습니다.

 

계산 후 가장 많은 화물을 가진 크레인의 cnt를 출력합니다.

---

#include <algorithm>
#include <iostream>
#include <vector>
#include <set>
using namespace std;




int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;
    vector<int> cranes(N, 0);
    for (int i = 0; i < N; ++i)
    {
        cin >> cranes[i];
    }
    sort(cranes.rbegin(), cranes.rend());


    int M;
    cin >> M;
    vector<int> weights(M, 0);
    for (int i = 0; i < M; ++i)
    {
        cin >> weights[i];
    }
    sort(weights.rbegin(), weights.rend());

    vector<int> cnts(N, 0);

    for (int i = 0; i < M; ++i)
    {
        if (weights[i] > cranes[0])
        {
            cout << -1;
            return 0;
        }
    }

    for (int i = 0; i < M; ++i) //weights
    {
        for (int j = 0; j < N; ++j)//cranes
        {
            if (j == N - 1 || cranes[j + 1] < weights[i] || cnts[j+1] > cnts[j])
            {
                ++cnts[j];
                break;
            }
        }
    }

    int result = 0;
    for (int i = 0; i < N; ++i)
    {
        result = max(result, cnts[i]);
    }

    cout << result;

    return 0;
}

역으로 정렬하고 비교하면 괜찮을 것이라는 느낌이 있어 다행히 이것이 답이되었지만 정확하게 왜 모든 경우에 부합하는지 설명은 좀 어렵네요