[백준] 1092번_배 C++

21 Mar 2023 in Study on Coding Test

정렬과 그리디 알고리즘을 사용해서 푸는 문제

정답제출코드

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

using namespace std;

int Crain, Box, minute = 0;
vector<int> CrainWeightLimit;
vector<int> BoxWeight;

int main()
{
    cin >> Crain;
    for (int i = 0; i < Crain; ++i)
    {
        int _input;
        cin >> _input;

        CrainWeightLimit.push_back(_input);
    }

    cin >> Box;
    for (int i = 0; i < Box; ++i)
    {
        int _input;
        cin >> _input;

        BoxWeight.push_back(_input);
    }

    sort(CrainWeightLimit.begin(), CrainWeightLimit.end(), greater<int>());
    sort(BoxWeight.begin(), BoxWeight.end(), greater<int>());

    // 가장 큰 박스 무게가 가장 큰 크레인의 제한을 초과할 경우 옮기지 못한다.
    if (BoxWeight[0] > CrainWeightLimit[0])
    {
        cout << -1;
        return 0;
    }

    while (!BoxWeight.empty())
    {
        for (int i = 0; i < Crain; ++i)
        {
            for (size_t j = 0; j < BoxWeight.size(); ++j)
            {
                if (CrainWeightLimit[i] >= BoxWeight[j])
                {
                    BoxWeight.erase(BoxWeight.begin() + j);
                    break;
                }
            }
        }
        minute++;
    }

    cout << minute;

    return 0;
}

우선, 내림 차순으로 박스의 무게들과 크레인의 제한을 정렬해주었다.

이 때, 가장 큰 박스 무게가 가장 큰 크레인의 제한을 초과할 경우 옮기지 못하므로

-1을 출력하고 끝내도록 하였다.

    sort(CrainWeightLimit.begin(), CrainWeightLimit.end(), greater<int>());
    sort(BoxWeight.begin(), BoxWeight.end(), greater<int>());

    // 가장 큰 박스 무게가 가장 큰 크레인의 제한을 초과할 경우 옮기지 못한다.
    if (BoxWeight[0] > CrainWeightLimit[0])
    {
        cout << -1;
        return 0;
    }

그리고 박스가 계속 남아있는 동안에 가장 큰 한도를 가진 크레인부터 무거운 박스부터 순서대로 옮기도록 하였다.

이 과정은 박스가 모두 없어질 때 까지 반복한다.

    while (!BoxWeight.empty())
    {
        for (int i = 0; i < Crain; ++i)
        {
            for (size_t j = 0; j < BoxWeight.size(); ++j)
            {
                if (CrainWeightLimit[i] >= BoxWeight[j])
                {
                    BoxWeight.erase(BoxWeight.begin() + j);
                    break;
                }
            }
        }
        minute++;
    }

그리고 2중 for문이 한번씩 돌 때마다 minute가 추가되도록 하였다.

오답제출코드(시간초과)

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

using namespace std;

int Crain, Box, minute = 0;
vector<int> CrainWeightLimit;
vector<int> BoxWeight;

int main()
{
    cin >> Crain;
    for (int i = 0; i < Crain; ++i)
    {
        int _input;
        cin >> _input;

        CrainWeightLimit.push_back(_input);
    }

    cin >> Box;
    for (int i = 0; i < Box; ++i)
    {
        int _input;
        cin >> _input;

        BoxWeight.push_back(_input);
    }

    sort(CrainWeightLimit.begin(), CrainWeightLimit.end(), greater<int>());
    sort(BoxWeight.begin(), BoxWeight.end(), greater<int>());

    while (!BoxWeight.empty())
    {
        for (int i = 0; i < Crain; ++i)
        {
            for (size_t j = 0; j < BoxWeight.size(); ++j)
            {
                if (CrainWeightLimit[i] >= BoxWeight[j])
                {
                    BoxWeight.erase(BoxWeight.begin() + j);
                    break;
                }
            }
        }
        minute++;
    }

    cout << minute;

    return 0;
}

가장 큰 무게를 가진 박스가 가장 큰 무게 한도를 가진 크레인보다 값이 클 때를 예외처리 해주지 않았다.

그래서 while문에서 무한루프가 걸려버려서 시간초과가 떠버렸다.