[백준 1092 - C++] 배 : 그리디 알고리즘

www.acmicpc.net/problem/1092

1092번: 배

문제

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

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

 

입력

첫째 줄에 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 각 크레인의 무게 제한이 주어진다. 이 값은 1,000,000보다 작거나 같다. 셋째 줄에는 박스의 수 M이 주어진다. M은 10,000보다 작거나 같은 자연수이다. 넷째 줄에는 각 박스의 무게가 주어진다. 이 값도 1,000,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 모든 박스를 배로 옮기는데 드는 시간의 최솟값을 출력한다. 만약 모든 박스를 배로 옮길 수 없으면 -1을 출력한다.

 

예제 입력 1 

3

6 8 9

5

2 5 2 4 7

예제 출력 1 

2

 

풀이

크레인이 효율적으로 움직이기 위해서는 무거운 물건을 들 수 있는 크레인이 무거운 물건을 들고, 상대적으로 가벼운 물건을 들 수 있는 크레인이 가벼운 물건을 들어야한다. 즉 다른 크레인이 일할 때 놀고 있는 크레인수를 최소화 해야한다.

따라서 크레인과 박스의 무게는 내림 차순으로 정렬하여 무거운 것부터 고려해야한다.

 

아예 크레인으로 움직일 수없는 경우는 가장 무거운 박스와 가장 무거운 크레인을 비교하는 것만으로 알 수 있다.

 

그런뒤 while문에서 크레인에 박스를 할당한다. 크레인에 할당된 박스의 경우엔 무게를 0으로 바꿔 다음에 고려하지 않아도 되게 구현하였다.

할당된 박스의 수를 up이라는 변수에 저장하여 모두 할당되는 경우 while문을 종료하게 한다.

 

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;

int cr[50];
int box[10000];

int main(void){
    int cr_n, box_n;
    int min_t = 0;
    int cr_index;
    int up =0;
    
    scanf("%d", &cr_n);
    for(int i=0; i<cr_n; i++){
        scanf("%d", &cr[i]);
    }
    
    scanf("%d", &box_n);
    for(int i=0; i<box_n; i++){
        scanf("%d", &box[i]);
    }
    
    sort(cr, cr + cr_n);
    sort(box, box + box_n);
    

    if(box[box_n-1] > cr[cr_n-1]){
        printf("-1\n");
        return 0;
    }
    
    while(up != box_n){
        min_t++;
        cr_index = cr_n-1;
        for(int i=box_n-1; i>=0; i--){
            if(box[i] == 0)
                continue;
            if(cr_index == -1)
                break;
            if(box[i] <= cr[cr_index]){
                cr_index--;
                up++;
                box[i] = 0;
            }
        }
        
    }
    printf("%d\n", min_t);
    
}