문제 이해 단계
문제 이해 자체는 간단하다. N대의 크레인이 있고, 각 크레인마다 무게제한이 존재한다.
이때 박스 K개가 주어지고, 각 크레인마다 하나씩 옮기는 데 걸리는 시간이 1분이다.
이 때, 총 걸리는 시간의 최솟값을 구하는 문제이다.
문제 접근 단계
포인트는 두 가지로 볼 수 있을 것 같다.
Point 1. 크레인 무게 제한
각자 들 수 있는 박스를 생각했을 때,
무게 제한이 클수록 들 수 있는 박스가 많아진다.
만약 무게 제한이 5와 3인 크레인이 있다면
3인 크레인은 1,2,3 밖에 못 들지만, 5인 크레인은 1,2,3,4,5까지 들 수 있다.
여기서 중요한 점은 5 크레인은
3 크레인의 박스를 들 수 있지만 그 반대는 안된다는 것이다.
5인 크레인은 3인 크레인에게 영향을 줄 수 있다.
그렇기 때문에 확실히 최솟값을 산출하기 위해서는
무게 제한이 높은 크레인부터 먼저 선택해야 한다.
Point2. 걸리는 시간
만약 두 개의 크레인이 있을 때 1번 크레인이 1분 만에 모든 작업을 마쳐도,
2번 크레인이 3분 걸린다면 총 소요시간은 3분이 된다.
즉, 소요시간은 가장 많은 작업을 한 크레인이 된다.
위 두 가지 포인트를 고려해 봤을 때, 크레인과 박스를 내림차순으로 정렬하는 것을 우선순위로 생각했다.
또한 크레인의 작업들은 동시에 이뤄진다.
3개의 크레인이 작업을 하는 횟수를 나타내면 1분 일 때 1,1,1이고
2분일 때 2,2,2 이런 식으로 작업을 해주어야 한다.
작업 횟수를 최소화하기 위해서는
모든 크레인이 박스를 최대한 비슷하게 드는 것이 중요하다.
만약 무게제한이 5인 크레인과 3인 크레인이 존재하고
박스가 1,2,3,4,5가 존재한다고 가정한다.
5 크레인과 4,5를 들 수 있지만, 3 크레인은 4,5를 들지 못한다.
박스를 최대한 일정하게 배분하기 위해서는,
겹치는 박스를 최대한 무게제한이 낮은 크레인이 들게 해야 한다.
왜냐하면 만약 5 크레인이 1,2,3 중 하나를 선택한다고 생각해 보자.
그렇게 되면, 3 크레인은 3번 작업할 수 있는 것을 2번밖에 작업하지 못한다.
그만큼 5 크레인이 추가적으로 작업해야 하기 때문이다.
이렇게 되면 총시간은 늘어날 수밖에 없다.
즉, 무게 제한이 높은 크레인부터 순서대로 돌아가면서 선택하는데,
자신이 들 수 있는 가장 무거운 박스부터 선택하면 된다.
문제 구현 단계
int N, M;
cin >> N;
vector <int> crain(N);
for (int i = 0; i < N; i++) cin >> crain[i];
cin >> M;
vector <int> weight(M);
for (int i = 0; i < M; i++) cin >> weight[i];
sort(crain.begin(), crain.end(),greater<int>());
sort(weight.begin(), weight.end(),greater<int>());우선 크레인과 무게의 배열을 입력받고
이를 내림차순으로 정렬한다.
if (crain[0] < weight[0]) {
cout << "-1";
return 0;
}만약 무게 제한이 가장 높은 크레인보다 무거운 것이 있으면,
이 작업은 완료할 수 없기 때문에 실패로 간주하고 -1을 출력하고 종료한다.
int answer = 0;
while (!weight.empty()) {
answer++;
for (int i = 0; i < N; i++) {
for (int j = 0; j < weight.size(); j++) {
if (crain[i] >= weight[j]) {
weight.erase(weight.begin() + j);
break;
}
}
}
}
cout << answer;자신이 들 수 있는 가장 무거운 무게를 찾는 작업을 하는 코드이다.
무게 제한이 높은 크레인부터 먼저 선택한다.
내림차순 정렬한 박스를 차례대로 확인한다.
해당 크레인보다 무게가 작거나 같다면 들 수 있는 것으로 간주하여 박스 리스트에서 지운 후,
다음 크레인이 작업하도록 차례를 넘긴다.
박스를 내림차순 정렬하여 0번째 인덱스부터 보게 했다.
그렇기 때문에 가장 처음 조건에 들어맞게
선택된 박스는 해당 상태에서 해당 크레인이 선택할 수 있는 가장 무거운 박스가 된다.
모든 크레인이 작업을 마치면 전체 작업이 1번 끝난 것이므로 answer++한다.
이 작업을 모든 박스가 없어질 때까지 실행한다.
아래는 전체 코드를 올리고 끝내겠다.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
cin.tie(NULL);
cout.tie(NULL);
ios::sync_with_stdio(false);
int N, M;
cin >> N;
vector <int> crain(N);
for (int i = 0; i < N; i++) cin >> crain[i];
cin >> M;
vector <int> weight(M);
for (int i = 0; i < M; i++) cin >> weight[i];
sort(crain.begin(), crain.end(),greater<int>());
sort(weight.begin(), weight.end(),greater<int>());
if (crain[0] < weight[0]) {
cout << "-1";
return 0;
}
int answer = 0;
while (!weight.empty()) {
answer++;
for (int i = 0; i < N; i++) {
for (int j = 0; j < weight.size(); j++) {
if (crain[i] >= weight[j]) {
weight.erase(weight.begin() + j);
break;
}
}
}
}
cout << answer;
return 0;
}
시행착오
이 문제를 오랜 시간 고민하고 여러 가지 방법을 사용해 봤지만,
예외케이스 때문에 틀리고, 예외케이스까지 맞는 로직을 찾으려니까 실패했다.
그래서 인터넷을 참고하였다.
대부분 저런 식으로 순회하는 방식을 사용했는데
놀랐던 점은 저게 시간초과가 뜨지 않는다는 점이었다.
저런 방식도 당연히 생각했지만,
반복문 중첩을 2번 이상 해야 하기 때문에 당연히 시간초과가 뜰 것이라고
생각하고 저 방법은 사용하지 않았다.
이런 걸 보면 시간 복잡도를 잘 계산하는 법을 알아야 할 것 같다.
그래야 반복문을 중첩으로 써도 시간이 남는지 아닌지 알지..
이 문제한테 호되게 혼난 것 같아서 반성하고 있다.