[BOJ 백준] 1092번 : 배 (C++, Python)

www.acmicpc.net/problem/1092

1092번: 배

 

그렇게 어려운 문제는 아니었는데 복잡하게 생각을 해서 그런가 헤매다가 다른 블로그의 글을 보고 푼 문제다.

 

문제는 단순하다. 각 크레인 마다 1개의 박스를 옮길 수 있고 무게 제한이 있다.

한 번 옮길 때 마다 크레인이 옮길 수 있는 최대 무게의 상자를 옮겨주면 된다.

 

 

 

문제 해결

• 가장 무거운 박스와 가장 무거운 무게를 들 수 있는 크레인을 비교한다.
  • 박스 값이 크레인 보다 크면 절대로 옮길 수 없는 박스이므로 -1을 출력하고 종료한다.
• 각 크레인 마다 들 수 있는 최대 무게의 상자를 옮긴다
  • 이 때, 가장 무거운 무게를 들 수 있는 크레인부터 확인을 하기 위해 크레인, 박스의 리스트는 내림차순으로 정렬한다.
• 옮겨진 상자는 리스트에서 삭제한다.
• 한 번에 하나의 상자만 옮길 수 있으므로 크레인이 상자를 옮겼다면 다음으로 넘어간다.
• 상자가 빌 때 까지 반복한다.

 

소스코드

C++

#include <bits/stdc++.h>
#define endl "\n"
#define MAX 10000
using namespace std;
int n, m;
int crane_weight, box_weight;
vector<int> cranes;
vector<int> boxes;
int answer = 0;
void prt(){
    for(int i=0; i<boxes.size(); i++){
        cout<<boxes[i]<<' ';
    }
    cout<<endl;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
   // freopen("input.txt", "r", stdin);
    cin >> n;
    for (int i = 0; i < n; i++) {  // 최대 50
        cin >> crane_weight;
        cranes.push_back(crane_weight);
    }
    cin >> m;
    for (int i = 0; i < m; i++) {  // 최대 10,000
        cin >> box_weight;
        boxes.push_back(box_weight);
    }
    sort(cranes.begin(), cranes.end(), greater<int>());
    sort(boxes.begin(), boxes.end(), greater<int>());
    if(boxes[0]>cranes[0]){cout<<-1; return 0;}
    while (!boxes.empty()){
        answer++;
        for(int i=0; i<cranes.size(); i++){
            for(int j=0; j<boxes.size(); j++){
                if(cranes[i]>=boxes[j]){ // 크레인이 박스를 들 수 있다면
                    boxes.erase(boxes.begin()+j); // 해당 위치의 박스 제거
                    break;
                }
            }
        }   
    }
    cout<<answer;
    return 0;
}

 

---

 

Python

import sys
read = sys.stdin.readline

N = int(read())
crane = list(map(int, read().split()))
M = int(read())
box = list(map(int, read().split()))

crane.sort(reverse=True)
box.sort(reverse=True)

if max(box) > max(crane):  # 담을 수 없는 경우
    print(-1)
    sys.exit()
else:
    answer = 0
    while(True):
        if not box: break  # 박스가 비어있지 않는 동안 실행
        for i in range(len(crane)):
            for j in range(len(box)):
                if crane[i] >= box[j]:
                    del box[j]
                    break
        answer += 1
print(answer)