[ 백준 ] 1092 / 배

金弘均·2021년 9월 15일
0

Baekjoon Online Judge

목록 보기
66/228
post-thumbnail

# Appreciation

/*
 * Problem :: 1092 / 배
 *
 * Kind :: Sorting + Greedy
 *
 * Insight
 * - 크레인을 무게 제한순으로 오름차순 정렬하고
 *   박스를 무게 오름차순으로 정렬해서
 *   무게제한이 작은 크레인부터 박스를 옮기고
 *   모든 크레인을 한 번씩 순회할 때마다 시간을 1분씩 증가시키면 될듯하다
 *   + 그런데... 이 생각엔 치명적인 오류가 있다
 *     2
 *     1 5
 *     6
 *     1 1 1 5 5 5
 *     # 위와같은 입력이 주어졌을 때
 *       첫 번째 생각으로는 올바른 답을 구할 수 없다
 *       크레인 / 박스
 *          1 / 1
 *          5 / 1 - 1분
 *          1 / 1
 *          5 / 5 - 2분
 *          1 / x
 *          5 / 5 - 3분
 *          1 / x
 *          5 / 5 - 4분
 *       총 4분이 걸리게 된다, 그러나
 *       크레인 / 박스
 *          1 / 1
 *          5 / 5 - 1분
 *          1 / 1
 *          5 / 5 - 2분
 *          1 / 1
 *          5 / 5 - 3분
 *       총 3분이 걸릴 수 있다
 *       -> 즉, 크레인은 자신의 무게제한 이하의 최대 무게의 박스를 옮겨야만
 *          걸리는 시간을 최소로 할 수 있다!
 *          => 그런 박스를 어떻게 찾을 수 있을까?
 *             lower_bound / x 이상이면서 가장 앞에 있는 원소
 *             upper_bound / x 초과이면서 가장 앞에 있는 원소
 *             prev(lower_bound) / x 미만이면서 가장 뒤에 있는 원소
 *             prev(upper_bound) / x 이하이면서 가장 뒤에 있는 원소
 *             ^= https://www.acmicpc.net/board/view/61980
 *             이를 활용해서 찾아주자!
 *
 * Point
 * - 남은 박스들의 무게가 어떤 크레인의 무게제한보다 크다면
 *   그 크레인을 없애줌으로써 연산량을 줄일 수 있다
 *   + 오름차순 정렬, pop_front 가 사용가능한
 *     Deque 을 활용했다
 */

# Code

//
//  BOJ
//  ver.C++
//
//  Created by GGlifer
//
//  Open Source

#include <iostream>
#include <deque>
#include <algorithm>

using namespace std;

#define endl '\n'

// Set up : Global Variables
/* None */

// Set up : Functions Declaration
/* None */


int main()
{
    // Set up : I/O
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // Set up : Input
    int N; cin >> N;
    deque<int> C(N);
    for (int i=0; i<N; i++)
        cin >> C[i];
    int M; cin >> M;
    deque<int> B(M);
    for (int i=0; i<M; i++)
        cin >> B[i];

    // Process
    sort(C.begin(), C.end()); /* 크레인들을 무게제한 오름차순으로 정렬 */
    sort(B.begin(), B.end()); /* 박스들을 무게 오름차순으로 정렬 */

    // Control : Output
    /* 무게제한이 가장 큰 크레인이 가장 무거운 박스의 무게보다 작다면 */
    if (C.back() < B.back()) {
        /* 박스를 모두 옮기는 것은 불가능 */
        cout << -1 << endl;
        exit(0);
    }

    // Process
    int ans = 0; /* 시간 */
    while (not(B.empty())) {
        ans++;
        int s = C.size(); /* 남은 크레인 개수 */
        while (s--) {
            int c = C.front(); /* 현재 크레인 무게제한 */
            C.pop_front();
            /* 현재 크레인 무게제한보다 큰 박스를 찾음 */
            auto pos = upper_bound(B.begin(), B.end(), c);
            /* pos 가 B.begin() 과 같다면
             * 모든 박스의 무게가 c 보다 커서 현재 크레인이 옮길 수 있는 박스는 없음 */
            if (pos == B.begin()) continue;
            B.erase(prev(pos)); /* prev(pos) = c 이하의 무게를 지닌
                                 * 가장 뒤의 박스를 삭제 */
            C.push_back(c); /* 사용한 크레인을 다시 넣어줌, 사용하지 않은 크레인은
                             * 후에도 다시 사용하지 않을 테니 넣어줄 필요 없음 */
        }
    }

    // Control : Output
    cout << ans << endl;
}

// Helper Functions
/* None */
profile
이런 미친 게임을 봤나! - 옥냥이

0개의 댓글