16237, bronze 1

16237번: 이삿짐센터

문제

• 1kg, 2kg, ..., 5kg 인 물건이 각각 $0\leq a,\ b,\ c,\ d,\ e \leq 1000$개 있다
• 물건들을 모두 옮기는데 최대 5kg 까지 담을 수 있는 바구니를 사용할 때 최소 몇 개가 필요한가?

 

$O(\mathrm{stuff_{max}}log\ \mathrm{stuff_{max}})$

Greedy
가장 무거운 물건을 우선으로 가방에 담는다
무거운 물건을 우선으로, 이미 물건이 담긴 가방에 담을 수 있다면 담고, 없다면 새로운 가방에 물건을 넣는다

 

Claim
최적 알고리즘을 사용하여 가방에 넣은 물건들의 자리를
사용한 가방의 개수 변화 없이 서로 바꿔서 greedy 알고리즘 결과와 같게 만들 수 있다

$pf.$
최적해의 각 가방에서 무거운 물건은 왼쪽에 오도록 정렬하자
또한 greedy 알고리즘에서 먼저 꺼낸 가방을 아래쪽에 위치하게 하고
각 가방에서 무거운 물건은 왼쪽에 오도록 한다

이제 아래에서 위로, 왼쪽에서 오른쪽으로 두 알고리즘의 해를 동시에 살펴보자
처음으로 서로다른 무게를 가진 물건 $S_{g},\ S_{o}$이 나왔다고 하자(greedy 알고리즘에서의 물건이 $S_{g}$)

i) $S_{g}>S_{o}$
물건의 자리를 옮길 때 가벼운 것을 큰 곳이 있던곳으로 옮기는 것은 문제되지 않으나
그 반대의 경우는 가방의 한계를 초과할 수 있기때문에 세밀하게 따진다

$S_{o}$을 포함하여 오른쪽에 있는 물건의 무게의 합은
가. $S_{g}$ 보다 가볍거나 같다
- 이 경우 최적알고리즘에서 $S_{g}$와 $S_{o}$을 포함한 오른쪽에 있는 물건의 위치를 바꾸면 된다
나. $S_{g}$ 보다 무겁다
먼저 최적해 알고리즘의 각 가방은 다음 구성 중 하나이다(또는 앞부분 일부)
$$\begin{aligned}
&\text{5}\\
&\text{4 1}\\
&\text{3 2}\\
&\text{3 1 1}\\
&\text{2 2 1}\\
&\text{2 1 1 1}\\
&\text{1 1 1 1 1}
\end{aligned}$$

$S_{g}$ 5와 1일 수 없다($\because$ case 분류에 따른 조건 위배)
$S_{g}$가 4인 경우 최적해에서는
$$\begin{aligned}
&\text{3 2}\\
&\text{3 1 1}\\
&\text{2 2 1}\\
&\text{2 1 1 1}\\
&\text{1 1 1 1 1}
\end{aligned}$$

중의 하나의 상태이다. 이때 앞부분의 일부를 더해 $S_{g}$와 같아지는 경우가 있으면
최적해에서 그 부분과 $S_{g}$를 바꾸면 된다

그 외의 경우인
$S_{g}=4$일 때 최적해가 3 2 인 경우를 따져보자
이때는 최적해에서 3 2 와 $S_{g}$가 들어있는 가방의 물건 전부의 위치를 바꿔준다

※위와 같이 해가 구성되면 다음 교환에서 Greedy 해의 위쪽에서 1을 빼가지고 $S_{g}$뒤로 옮기면 된다

$S_{g}$가 3인 경우 최적해에서는
$$\begin{aligned}
&\text{2 2}\\
&\text{2 2 1}\\
&\text{2 1 1}\\
&\text{2 1 1 1}\\
&\text{1 1 1 1}\\
&\text{1 1 1 1 1}
\end{aligned}$$

중의 하나의 상태이다. 이때 앞부분의 일부를 더해 $S_{g}$와 같아지는 경우가 있으면
최적해에서 그 부분과 $S_{g}$를 바꾸면 된다

그 외의 경우인
$S_{g}=3$일 때 최적해가 2 2 이거나 2 2 1 인 경우를 따져보자
먼저 2 2 이면

최적해에서 $S_{o}$와 $S_{g}$를 바꿔주면 된다

2 2 1 이면

이 경우도 역시 최적해에서 $S_{o}$와 $S_{g}$를 바꿔주면 된다

$S_{g}$가 2인 경우 최적해에서는
$$\begin{aligned}
&\text{1 1 1}\\
&\text{1 1 1 1}\\
&\text{1 1 1 1 1}\\
\end{aligned}$$

중의 하나의 상태이다. 모두 앞부분의 일부를 더해 $S_{g}$와 같아지는 경우가 있고
최적해에서 그 부분과 $S_{g}$를 바꿔주면 된다

ii) $S_{g}<S_{o}$
이러한 경우는 존재하지 않는다
greedy 알고리즘에서는 무게가 더 무거운 물건을 먼저 배정하므로 $S_{o}$ 가 더 무겁다면
$S_{o}$ 이후에 $S_{g}$를 배정하게 된다
$S_{o}$를 배정 할 시점을 생각하자
$S_{g}$자리는 $S_{o}$ 이상 무게의 물건이 배정되어 있거나 비어있어야 한다□

#include <bits/stdc++.h>
#define endl "\n"
#define loop(i, n) for(int i = 1; i <= n; i++)
using namespace std;
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
 
    int stuff[6];
    loop(i, 5) cin >> stuff[i];
 
    priority_queue<int> bag;
    bag.push(5);
    int w = 5;
    while(w > 0){
        if(stuff[w]){
            int remain = bag.top();
            if(remain >= w){
                bag.pop();
                bag.push(remain - w);
            }
            else bag.push(5-w);
            stuff[w]--;
        }
        else w--;
    }
 
    cout << bag.size() << endl;
 
    return 0;
}cs