[BOJ/백준][Gold5] 1092 : 배 (C++)

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

1092번: 배

 

[난이도] Gold5
[유형] Greedy

[풀이]
크레인의 용량과 박스의 크기를 내림차순을 해준 뒤
1번의 사이클에서 가장 들 수 있는 무게가 큰 크레인부터 가장 큰 박스를 매칭시켜주면 된다.
만약 박스가 선택되었으면 erase 연산으로 vector에서 지워주면서 반복한다.

 

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
int N,M;
vector<int> a,b;
bool cmp(int a,int b){
    return a>b;
}
int main(){
    scanf("%d",&N);
    a.resize(N);
    for(int i=0;i<N;i++) scanf("%d",&a[i]);
    scanf("%d",&M);
    b.resize(M);
    for(int i=0;i<M;i++) scanf("%d",&b[i]);
 
    sort(a.begin(),a.end(),cmp);
    sort(b.begin(),b.end(),cmp);
    if(a[0]<b[0]) {
        puts("-1");
        return 0;
    }
    int ans =0;
    while(b.size()!=0){
        for(int i=0;i<a.size();i++){
            for(int j=0;j<b.size();j++){
                if(a[i]>=b[j]){
                    b.erase(b.begin()+j);
                    break;
                }
            }
        }
        ans++;
    }
    printf("%d",ans);
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold5/1092.cpp