[백준/C++] 1092번 배

1.문제 링크

1092

2. 풀이 전 계획과 생각

• 그리디 알고리즘으로 풀기

3. 풀이

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

bool compare(int i, int j){
    return i>j;
}

int max_value(vector<int> &v, int n){
    int maxValue = v[0];
    for(int i=0;i<n;i++){
        if(maxValue<v[i]) maxValue=v[i];
    }
    return maxValue;
}


int main(){
    int n; cin>>n;
    vector<int> crane(n);

    // 크레인 무게 제한 입력
    for(int i=0;i<n;i++) cin>>crane[i];
    
    int m; cin>>m;
    vector<int> box(m);

    // 박스 무게 입력
    for(int i=0;i<m;i++) cin>>box[i];
    
    // 박스, 크레인 최대 무게 구하기
    int craneMaxValue = max_value(crane, n);
    int boxMaxValue = max_value(box, m);
    
    // 박스 최대 무게가 크레인 최대 무게보다 크다면
    if(craneMaxValue<boxMaxValue){
        cout<<-1;
        return 0;
    }
    
    // 크레인, 박스 배열 내림차순 정렬 
    sort(crane.begin(), crane.end(), compare);
    sort(box.begin(), box.end(), compare);
    
    int min=0;
    while(true){
        for(int i=0;i<n;i++){
            for(int j=0;j<box.size();j++){
                if(box[j]<=crane[i]){
                    box.erase(box.begin()+j);
                    break;
                }
            }
            if(box.size()==0) break;
        }
        min++;
        if(box.size()==0) break;
    }
    
    // 답 입력
    cout<<min;
}

1. 크레인 최대 무게 제한과 박스 중 최대 무게를 구한다. 여기서 박스 최대 무게가 크레인 최대 무게보다 크면 박스를 배로 옮길 수 없으므로 -1을 출력한다.

2. 크레인, 박스 배열을 내림차순으로 정렬

3. n개의 크레인에 최대 m개의 박스를 비교하면서 박스 무게가 크레인 무게 중량보다 작거나 같으면 box 벡터에서 지워주기.

4. 박스 배열 크키가 0이라면(비어있다면) while 무한 반복문에서 빠져나가기.

4. 풀이하면서 고민했던 점

• while 무한 반복문 코드를 구현하는 방법을 고민함.

5. 문제를 풀고 알게된 개념 및 소감

• 그리디 알고리즘에 대한 이해도가 올라감.