백준 1092 c++ "배" -PlusUltraCode-

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

[필자 사고]

그리디 알고리즘이다..

필자는 처음에 binary_search()를 이용하려 풀라 했찌만 답이 안나왔다.

고민을 해보니 반복문 및 조건을 잘 명시하면 풀 수 있을거 같았다.

일단 두 배열을 내림차순으로 정렬한 뒤

각 idx를 순차적으로 점검했다. for(int i=0;i<M && idx<N; i++) 이 반복문을 보면

박스의 i와 화물의 idx 를 서로 조건문을 맏는 for문이다. 매력적인 느낌이 든다.

 

위와 같은 형태로 moved 를 증가시켜 바깥 while(moved<M) 형태로 해당 문제를 타파했다.

 

아래는 자세한 코드 해설이다.

[코드 해설]

코드 해설 (함수: main)

1. 입력 처리
   • 먼저 크레인의 개수 N을 입력받습니다.
   • 이어서 각 크레인의 무게 제한을 벡터 cranes에 저장합니다.
   • 박스의 개수 M을 입력받고, 각 박스의 무게를 벡터 boxes에 저장합니다.
2. 정렬
   • cranes와 boxes를 모두 내림차순으로 정렬합니다.
   • 이렇게 하면 가장 무거운 박스와 가장 센 크레인을 먼저 매칭할 수 있습니다.
3. 불가능한 경우 판정
   • 가장 무거운 박스가 가장 센 크레인보다 무거우면 절대 옮길 수 없습니다.
   • 이 경우 -1을 출력하고 프로그램을 종료합니다.
4. 시뮬레이션 준비
   • time을 0으로 초기화합니다. 이 변수는 총 경과 시간을 기록합니다.
   • used라는 불리언 벡터를 만들어 박스가 옮겨졌는지를 표시합니다.
   • moved라는 정수를 0으로 두어 옮겨진 박스의 개수를 기록합니다.
5. 라운드별 시뮬레이션
   • 모든 박스가 옮겨질 때까지 while 루프를 반복합니다.
   • 각 라운드에서 모든 크레인이 동시에 박스를 옮길 수 있으므로, for 루프를 돌며 크레인마다 조건에 맞는 박스를 찾습니다.
   • 크레인의 무게 제한이 현재 박스의 무게보다 크거나 같고, 아직 옮겨지지 않은 박스라면 그 박스를 옮겼다고 표시하고(used[i] = true), moved를 증가시킵니다.
   • 한 크레인은 한 라운드에 한 박스만 옮길 수 있으므로, 박스를 옮기면 다음 크레인으로 넘어갑니다.
   • 라운드가 끝나면 time을 1 증가시킵니다.
6. 결과 출력
   • 모든 박스가 옮겨졌을 때 루프가 끝나고, 총 걸린 시간을 time에 담아 출력합니다.

[소스 코드]

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

int main() {
    int N, M;
    cin >> N;
    vector<int> cranes(N);
    for (int i = 0; i < N; i++) cin >> cranes[i];

    cin >> M;
    vector<int> boxes(M);
    for (int i = 0; i < M; i++) cin >> boxes[i];

    sort(cranes.begin(), cranes.end(), greater<int>());
    sort(boxes.begin(), boxes.end(), greater<int>());

    if (boxes[0] > cranes[0]) {
        cout << -1;
        return 0;
    }

    int time = 0;
    vector<bool> used(M, false);
    int moved = 0;

    while (moved < M) {
        int idx = 0;
        for (int i = 0; i < M && idx < N; i++) {
            if (!used[i] && cranes[idx] >= boxes[i]) {
                moved++;
                used[i] = true;
                idx++;
            }
        }
        time++;
        
   }

    cout << time;
    return 0;
}