https://www.acmicpc.net/problem/1092
이 문제는 그리디이다 이문제는 얼피하면 그냥 정렬한후 처리처리 하게 하는거로 생각해서 틀릴 수가 있다 이문제의 경우 최소의 해를 그리디로 만족 시키기위해서는 큰 화물을 처리할 수 있는 화물은 최대한 큰것 부터 처리 해야한다는 것이다
백준에서 제공 하는 3번 input을 이용해서 보자
이렇게 테스트 케이스가 주어졌을때
Krane 을 처리 할 수 있는 무게에 따라 오름 차순 정렬해주면
23 25 28 32 이렇게 정렬이 된다
이제 화물을 오름 차순으로 정렬해보자
2 5 7 10 16 18 20 24 27 32 이렇게 정렬이 된다.
이후 3번째 크레인이 처리 할수 있는 최대 무게는 32 임으로 해당 크레인은 일단 32를 처리 한다
2번 째크레인은 27을 처리하고 1번째 크레인은 24를 0번째 크레인은 23을 처리한다
이렇게 처리하면 1초가 지나간다
그 후 크레인은 내가 현재 보고있는 화물이 이미 처리되어있으면 다음 화물을 처리하기 위해서 내가 지금 있는 위치에서 이전 위치까지 탐색하다 화물이 안처리되었으면 처리하면 된다 이렇게 로직이 가능한 이유는 오름차순 정렬을 했기 때문에 내가 처리한 화물 이전에 있는 화물들은 다처리 할 수 있기 때문이다
코드는 아래와 같다
#include<iostream>
#include<algorithm>
using namespace std;
int krane[50];
int cargo[10000];
int kraneidx[50];
bool isDo[10000];
// 각 Krane이 처리할수 있는 최대 무게의 index저장
int clear;
int n, m;
int main() {
cin >> n;
for (int i = 0; i < n; i++) {
cin>>krane[i];
}
cin >> m;
for (int i = 0; i < m; i++) {
cin>>cargo[i];
}
sort(krane, krane + n);
sort(cargo, cargo + m);
if (krane[n - 1] < cargo[m - 1]) {
cout << -1;
return 0;
}
int maxKrane = n - 1;
for (int i = m - 1; i >= 0; i--) {
if (maxKrane < 0)
break;
if (krane[maxKrane] >= cargo[i]) {
kraneidx[maxKrane] = i;
maxKrane--;
}
}
for (int i = 0; i <= maxKrane; i++) {
kraneidx[i] = -1;
}
int cnt = 0;
maxKrane = kraneidx[n - 1];
while (maxKrane > 0) {
maxKrane = kraneidx[n - 1];
for (int i = n - 1; i >= 0; i--) {
if (kraneidx[i] < 0)
continue;
if (!isDo[kraneidx[i]]) {
isDo[kraneidx[i]] = true;
}
else {
while (isDo[kraneidx[i]] && kraneidx[i]>=0) {
kraneidx[i] -= 1;
}
if(kraneidx[i] >= 0)
isDo[kraneidx[i]] = true;
}
}
if (kraneidx[n - 1] < 0)
break;
cnt += 1;
}
cout << cnt;
}'백준(코테준비) > 그리디' 카테고리의 다른 글
| 백준 2212 / cpp / c++ (0) | 2024.12.17 |
|---|---|
| 백준 1700 / C++ (0) | 2024.12.09 |
| 백준 12904 (0) | 2024.08.09 |
| 백준 2812 / C++ (0) | 2024.08.03 |
| 백준 1744 (0) | 2024.07.27 |
