[ 백준 BOJ ] 1092번 - 배 (C++)

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

 

생각 흐름

• 처음엔 간단하게 크레인과 박스를 내림차순 정렬하고 하나씩 뽑으면 되겠네 하고 제출했지만 실패
  
  • 2
  • 21 19
  • 4
  • 20 20 18 7
  • 위와 같은 경우 답은 2이지만, 출력은 3으로 나왔다.
• N은 50이고 M은 10,000이기에 그냥 이중 for 문으로 돌리면서 각 크레인이 집을 수 있는 박스들을 선정해주었다.

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

using namespace std;

int N;
vector<int> crane;
int M;
vector<int> box;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin>>N;
    
    int tmp;
    for(int i = 0; i<N; i++){
        cin>>tmp;
        
        crane.push_back(tmp);
    }
    
    cin>>M;
    
    for(int i = 0; i<M; i++){
        cin>>tmp;
        
        box.push_back(tmp);
    }
    
    sort(crane.rbegin(), crane.rend());
    sort(box.rbegin(), box.rend());
    
    if(crane[0] < box[0]){
        cout<<-1<<endl;
        
        return 0;
    }
    
    int answer = 0;
    int carryCount = 0;
    while(carryCount!=M){
        answer++;
        
        int craneIdx = 0;
        for(int i = 0; i<M; i++){
            if(box[i]!=-1){
                if(box[i]<=crane[craneIdx]){
                    box[i] = -1;
                    carryCount++;
                    craneIdx++;
                }
            }
            if(craneIdx>=N) break;
        }
    }
    
    cout<<answer<<endl;
    
    return 0;
}